单词拆分
(这个递推还是挺抽象的,不太好理解)
注意是需要词语的顺序,因此这是一个排列问题,所以外层循环是背包,内层循环是物品。
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> bags(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for(int i = 1;i <= s.size(); i++){
for(int j = 0; j < i; j++){
string word = s.substr(j, i - j);
if(bags.find(word) != bags.end() && dp[j] == true)
dp[i] = true;
}
}
return dp[s.size()];
}
多重背包
多重背包和01背包的区别在于:对于每个不同的物品,有一个数量限制,既不是只能用一次,又不是可以无限使用。
解法比较简单,就是把每个物品拆分成单个物品,然后就转换为了01背包问题。