代码随想录day46动态规划part08

139.单词拆分

判断一个单词能否用空格拆分为字典里的单词
动规五部曲：1.dp[j]单词的前j个长度拆分出的单词是否都在字典里
2.公式：if(j>=i && dp[i] && worddict.find(dp[j-i])!=end()) dp[j]=true;
3.初始化：dp[0]=true;dp[i]=false;
4.遍历顺序：完全背包内嵌的for循环为正序；这是排列数所以外层背包内层物品

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(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); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

多重背包理论

把多重背包拆成0，1背包