今日任务：

1. 多重背包
2. LeetCode139 单词拆分
3. 背包问题总结

资料来源：

1. 代码随想录 | 多重背包
2. 代码随想录 | LeetCode139 单词拆分
3. 代码随想录 | 背包问题总结

1 多重背包问题

多重背包，是在01背包的基础上，要求每种物品可以有x件，且每种物品数量可以不同。

多重背包的解法一般有两种：

1. 多重背包拆为01背包：既然每种物品数量不唯一，那把这些物品都看成不同的种类就可以了。比如说有物品一3件，物品二2件，那么拆成01背包的话就是物品一、物品一、物品一、物品二、物品二，再按01背包来就行了。
2. 将多的物品分拆成多个背包，分别计算，最后再合并。

2 LeetCode139 单词拆分

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

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

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

这是多重背包吗？

要记录的状态就是对于s来说，从0到i的字符能不能被字典中的单词组成。状态推导就是对于每个i，循环匹配s中字符i - len(word)到字符i之间组成的单词和字典中的词语是否匹配，外加这个i - len(word)是否为true。如果两个都为true，则i处的状态为true。

go
func wordBreak(s string, wordDict []string) bool {
	dpArray := make([]bool, len(s) + 1)
	dpArray[0] = true
	for i := 1; i <= len(s); i++ {
		for _, word := range wordDict {
			if i < len(word) {
				continue
			}
			dpArray[i] = dpArray[i - len(word)] && s[i - len(word) : i] == word
			if dpArray[i] == true { // 写法问题 我这是直接赋值 还有可能出现已经赋值为true了 不停止循环的话待会又被赋回false的情况
				break
			}
		}
	}
	return dpArray[len(s)]
}

3 背包问题总结

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])

01背包：注意一维对背包进行遍历时，是反向遍历。

完全背包：注意一维对背包进行遍历时，是正向遍历。求组合数就是先物品后背包，求排列数就是先背包再物品。