LC139. 单词拆分
dp[i]含义 : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词
遍历顺序：如题说，是拆分为一个或多个在字典中出现的单词，所以这是完全背包
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题其实我们求的是排列数，为什么呢。 拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。
"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。
"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。
所以说，本题一定是 先遍历 背包，再遍历物品。
bool wordBreak(string s, vector<string>& wordDict)
{
int size = s.size();
unordered_set<string> uset(wordDict.begin(), wordDict.end());
vector<bool> dp(size + 1, false);
dp[0] = true;
for (int i = 1; i <= size; ++i)
{
for (int j = 0; j < i; ++j)
{
string str = s.substr(j, i - j);
if (uset.find(str) != uset.end() && dp[j])
{
dp[i] = true;
}
}
}
return dp[size];
}