【动态规划】139. 单词拆分、多重背包

提示：努力生活，开心、快乐的一天

---

139. 单词拆分

题目链接：139. 单词拆分

💡解题思路

1. 转化为背包问题：单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词，说明就是一个完全背包！
2. 动规五部曲：

• 确定dp数组以及下标的含义：dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
• 确定递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
• dp数组如何初始化：，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了
• 确定遍历顺序：本题其实我们求的是排列数。外层for遍历背包，内层for循环遍历物品。
  拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
  “apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
  “apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。
• 举例推导dp数组：按照递推公式推导一下做推导，如果发现结果不对，就把dp数组打印出来

🤔遇到的问题

1. 遍历单词的时候总是忘记是一个数组形式的单词

💻代码实现

动态规划

var wordBreak = function (s, wordDict) {
    let dp = new Array(s.length+1).fill(false)
    dp[0] = true
    //先遍历背包，在遍历物品
    for (let i = 0; i <= s.length; i++) {
        for (let j = 0; j < wordDict.length; j++) {
            if (i >= wordDict[j].length) {
                if (s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) {
                    dp[i] = true
                }
            }
        }
    }
    console.log(dp)
    return dp[s.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🎯题目总结

本题转化为背包问题，需要转化思路，要不然不容易想到
如果先遍历物品再遍历背包会有什么问题呢？
使用用例：s = “applepenapple”, wordDict = [“apple”, “pen”]，对应的dp数组状态如下：

最后dp[s.size()] = 0 即 dp[13] = 0 ，而不是1，因为先用 “apple” 去遍历的时候，dp[8]并没有被赋值为1 （还没用"pen"），所以 dp[13]也不能变成1。
除非是先用 “apple” 遍历一遍，再用 “pen” 遍历，此时 dp[8]已经是1，最后再用 “apple” 去遍历，dp[13]才能是1。

---

多重背包

无具体题目
题意：有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

💡解题思路

1. 例如：
   背包最大重量为10。
   物品为：
   重量 价值 数量
   物品0 1 15 2
   物品1 3 20 3
   物品2 4 30 2
   问背包能背的物品最大价值是多少？
   和如下情况有区别么？
   重量 价值 数量
   物品0 1 15 1
   物品0 1 15 1
   物品1 3 20 1
   物品1 3 20 1
   物品1 3 20 1
   物品2 4 30 1
   物品2 4 30 1
   毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
   也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。

🎯题目总结

多重背包在面试中基本不会出现，力扣上也没有对应的题目，大家对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了。

🎈今日心得

背包问题总结篇