題目描述
有一個很長的由小寫字母組成字符串。為了便于對這個字符串進行分析，需要將它劃分成若干個部分，每個部分稱為一個單詞。出于減少分析量的目的，我們希望劃分出的單詞數越少越好。你就是來完成這一劃分工作的。
輸入
第一行，一個字符串。（字符串的長度不超過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;
}
)
