算法思想：
完全背包中的排列问题。
dp[j] 表示长度位j的字符串是否可以由字典组成。
写法一：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<int> dp(s.size()+1, false);
dp[0] = true;
//是个排列问题，先遍历背包，再遍历物品
for(int j=1;j<=s.size();j++)
{
for(int i=0;i<wordDict.size();i++)
{
if(j<wordDict[i].size())
continue;
string news = s.substr(j-wordDict[i].size(), wordDict[i].size());
if(news == wordDict[i] && dp[j-wordDict[i].size()])
{
dp[j] = true;
}
}
}
return dp[s.size()];
}
};
写法二：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<int> dp(s.size()+1, false);
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
dp[0] = true;
//是个排列问题，先遍历背包，再遍历物品
for(int j=1;j<=s.size();j++)
{
for(int i=0;i<j;i++)
{
string wupin = s.substr(i, j-i);
if(wordSet.find(wupin)!=wordSet.end() && dp[i])
{
dp[j] = true;
}
}
}
return dp[s.size()];
}
};
