动态规划的第六篇！背包问题总结篇！

322. 零钱兑换

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。但是如何找最小的“组合”呢？（通过dp数组的不同定义与递推公式）

确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]

递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标对应的数值呢？考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

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

举例推导dp数组

略

以先遍历物品、后遍历背包为例

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1)  # 创建动态规划数组，初始值为正无穷大dp[0] = 0  # 初始化背包容量为0时的最小硬币数量为0for coin in coins:  # 遍历硬币列表，相当于遍历物品for i in range(coin, amount + 1):  # 遍历背包容量# 注意这个for循环的“剪枝”if dp[i - coin] != float('inf'):  # 如果dp[i - coin]不是初始值，则进行状态转移dp[i] = min(dp[i - coin] + 1, dp[i])  # 更新最小硬币数量if dp[amount] == float('inf'):  # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解return -1return dp[amount]  # 返回背包容量为amount时的最小硬币数量

279.完全平方数

题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

确定dp数组（dp table）以及下标的含义

dp[j]：和为j的完全平方数的最少数量为dp[j]

确定递推公式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

dp数组如何初始化

dp[0]表示和为0的完全平方数的最小数量，那么dp[0]一定是0。

从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

确定遍历顺序

最小组合，和上题一样

所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

举例推导dp数组

略

class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1):  # 遍历背包for j in range(1, int(i ** 0.5) + 1):  # 遍历物品 # 注意对j的取值范围进行开根号的限制# 更新凑成数字 i 所需的最少完全平方数数量dp[i] = min(dp[i], dp[i - j * j] + 1)# 注意这个位置使用的是j * jreturn dp[n]

139.单词拆分

动态规划

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包！

确定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了。

确定遍历顺序

拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

"apple", "pen" 是物品，那么我们要求物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。

"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是先遍历背包，再遍历物品。

换而言之，就是题目中的字符串中单词元素可能出现在多个位置，所以不能先遍历物品，不然物品就被消耗掉了，按序遍历到后面就没有物品可用了

举例推导dp[i]

略

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)n = len(s)dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词dp[0] = True  # 初始状态，空字符串可以被拆分成单词for i in range(1, n + 1): # 遍历背包for j in range(i): # 遍历单词if dp[j] and s[j:i] in wordSet:dp[i] = True  # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词# 防止被覆盖breakreturn dp[n]

回溯解法

递归终止条件

if startIndex >= len(s):return True

递归逻辑

从 startIndex 开始，尝试所有可能的拆分位置 i
截取从 startIndex 到 i 的子串作为候选单词
如果这个候选单词在字典中存在，并且从 i+1 位置开始的剩余字符串也能被成功拆分（递归调用的结果为 True），则返回 True

class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:# 边界情况：已经遍历到字符串末尾，返回Trueif startIndex >= len(s):return True# 遍历所有可能的拆分位置for i in range(startIndex, len(s)):word = s[startIndex:i + 1]  # 截取子串if word in wordSet and self.backtracking(s, wordSet, i + 1):# 如果截取的子串在字典中，并且后续部分也可以被拆分成单词，返回Truereturn True# 无法进行有效拆分，返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)  # 转换为哈希集合，提高查找效率return self.backtracking(s, wordSet, 0)

多重背包（了解即可）

之前我们学了01背包、完全背包，现在我们来看一下多重背包的概念和题目

56. 携带矿石资源（第八期模拟笔试）

多重背包和01背包是非常像的，为什么和01背包像呢？每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

C, N = input().split(" ")
C, N = int(C), int(N)# value数组需要判断一下非空不然过不了
weights = [int(x) for x in input().split(" ")]
values = [int(x) for x in input().split(" ") if x]
nums = [int(x) for x in input().split(" ")]dp = [0] * (C + 1)
# 遍历背包容量
for i in range(N):for j in range(C, weights[i] - 1, -1):for k in range(1, nums[i] + 1):# 遍历 k，如果已经大于背包容量直接跳出循环if k * weights[i] > j:breakdp[j] = max(dp[j], dp[j - weights[i] * k] + values[i] * k) 
print(dp[-1])