代码随想录算法训练营第四十天|139.单词拆分，多重背包，背包问题

139. 单词拆分 - 力扣（LeetCode）

给你一个字符串?s?和一个字符串列表?wordDict?作为字典。请你判断是否可以利用字典中出现的单词拼接出?s?。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple"可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

思路：完全背包问题，单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。转换成背包问题有两个难点：①dp[i]是如何来的，②遍历顺序。

解决：动态规划五步曲

? ? ? ? 1.确定dp[j]的含义；

????????dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

? ? ? ? 2.确定dp[j]递推公式；

? ? ? ? 这里递推公式好像和之前不同，这里既没有01背包的价值，又没有完全背包的组合数量，通过dp[j]的含义我们知道，dp[i]要不就是true，要不就是false，我们要的就是true。

? ? ? ??如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

? ? ? ? 到这里有点懵了，i是字符串长度，那j是什么，j这里其实表示当前遍历字符串中的位置。

? ? ? ? 举个例子：s = "leet", wordDict = ["le", "et"]

? ? ? ? i等于1时，j就从0开始，j=0时，截取i-j就是le，发现wordDict中有“le”，所以dp[i]=true。

? ? ? ? 3.确定dp初始化；

? ? ? ? 没开始前，dp[i]=false，但是从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了

? ? ? ? 4.确定遍历顺序；

? ? ? ? 从上面分析可知，随着字符串长度i增大，依次遍历，能在wordDict中找到的单词肯定越多，结果也越有可能是true。，所以本题一定是先遍历背包，再遍历物品。

? ? ? ? 举个例子：拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

????????"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

? ? ? ? 5.举例推导dp数组。

????????以输入: s = "leetcode", wordDict = ["leet", "code"]为例，dp状态如图：

代码：这里利用unordered_set判断是否在wordDict中找到单词。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0]=true;
        for(int i=0;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[j]表示前j个长度的字符串可以由单词拼接，并且截取的子字符串在数组中
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];
    }
};

多重背包

????????例题：有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

????????区别：多重背包和01背包是非常像的，每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

????????面试基本不会考，了解即可。

背包问题总结

难点：递推公式和遍历顺序

步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

递推公式总结：

? ? ? ? 1.问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

? ? ? ? 2.?问装满背包有几种方法：dp[j] += dp[j - nums[i]]?

? ? ? ? 3.问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

? ? ? ? 4.问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

遍历顺序总结：

? ? ? ? 1.01背包

? ? ? ? ①二维数组：二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

? ? ? ? ②一维数组：一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

? ? ? ? 2.完全背包

? ? ? ? ①如果求组合数就是外层for循环遍历物品，内层for循环遍历背包。

? ? ? ? ②如果求排列数就是外层for循环遍历背包，内层for循环遍历物品。

总结：对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。