单词的划分（动态规划）

题目描述

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入

第一行，一个字符串。（字符串的长度不超过300）
第二行一个整数n，表示单词的个数。（n≤100）
第3~n+2行，每行列出一个单词。

输出

一个整数，表示字符串可以被划分成的最少的单词数

样例输入

realityour
5
real
reality
it
your
our

样例输出

2

思路分析

读入数据：字符串s，n个单词，单词存入set容器。

动态规划。

dp[i]表示前i个字符可以被划分成的最少的单词数。

考虑数据规模，初始化dp数组大小为len+1（len=s.size()），各元素大小为1000，但dp[0]=0。

i从0遍历到len。

对于任意i，如果dp[i]=1000，证明前i个字符没有最小划分；否则，遍历wordset中的单词，compare找到字符串s从位置i开始能够匹配的单词t，更新dp[i+t.size()]=min(dp[i]+1,dp[i+t.size()])。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s,word;
int len,n;
set<string>wordset;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>s;len=s.size();cin>>n;for(int i=1;i<=n;i++){cin>>word;wordset.insert(word);}vector<int>dp(len+1,1000);dp[0]=0;for(int i=0;i<=len;i++){if(dp[i]==1000)continue;for(string t:wordset){int lt=t.size();if(i+lt<=len&&s.compare(i,lt,t)==0){dp[i+lt]=min(dp[i]+1,dp[i+lt]);}}}cout<<dp[len];return 0;
}