一、322. 零钱兑换
322. 零钱兑换如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这句话结合本题 大家要好好理解。
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
代码随想录
1. 解题思路
（1）DP数组的含义：装满容量为 j 的背包，最少物品为DP[j]，最终要求DP[amount]。
（2）递推公式：dp[j] = min(dp[j], dp[ j-coins[i] ] + 1)
（3）初始化：DP[0] = 0，非0下标初始为非0最大值，这样在递推过程中不会被0覆盖。
（4）遍历顺序：本题求装满背包的最小元素数量，所以本题的遍历顺序无论是先遍历顺序还是背包都没有影响，也就是求排列数或者组合数都没有影响。
（5）打印DP数组。
2. 代码实现
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount+1)dp[0] = 0for i in coins:for j in range(i, amount+1):dp[j] = min(dp[j], dp[j-i]+1)if dp[amount] == float('inf'):return -1return dp[amount]
二、279.完全平方数
279.完全平方数本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
代码随想录
1. 解题思路
如果拼凑不成应该返回什么？本题无需考虑这种情况，因为有1的存在，所以任何一个正整数都可以由完全平方数去进行拼凑得到。
2. 代码实现
class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n+1):j = 1while j * j <= i:dp[i] = min(dp[i], dp[i - j*j]+1)j += 1return dp[n]
三、139.单词拆分
139.单词拆分视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili
代码随想录
1. 解题思路
（1）定义dp数组的含义：字符串长度为 i，能被下面单词组成的话，dp[i]就为True，bool类型。
（2）递推公式：dp[i]是True or False依赖于哪些状态：如果区间j到i出现在单词里，同时dp[j]为True，则dp[i]就为True。
（3）dp数组初始化：dp[0] = True保证后面递推不全是False，非0下标初始化为False。
（4）遍历顺序 ：因为字符串里面的单词组合是有序的，所以本题对物品的顺序是有要求的，不能随意置换遍历顺序。本题先遍历背包再遍历物品，先截取物品，再判断截取的这个物品是否出现在字典里，如果在字典里并且dp[i] == True，那么dp[j] == True。
（5）打印dp数组。
2. 代码实现
- 初始化动态规划数组
dp：dp = [False] * (len(s)+1)：创建一个长度为len(s)+1的布尔数组dp，所有元素初始化为False。这里数组的长度是len(s)+1是因为我们需要考虑从字符串的起始位置（索引0）到结束位置（索引len(s)-1）的所有子串，以及一个额外的空子串（索引0表示的情况）。dp[0] = True：设置dp[0]为True表示空字符串可以被成功拆分（因为没有字符需要拆分）。
- 动态规划过程：
- 外层循环
for i in range(1, len(s)+1)：遍历字符串s的所有可能结束位置（从索引1到len(s)）。 - 内层循环
for word in wordDict：遍历字典wordDict中的所有单词。 - 判断条件
if i >= len(word)：确保当前考虑的子串s[i-len(word):i]的长度至少与单词word一样长。 - 状态转移方程
dp[i] = dp[i] or (dp[i-len(word)] and word == s[i-len(word):i])：如果dp[i-len(word)]为True（表示子串s[0:i-len(word)]可以被成功拆分），并且当前考虑的单词word等于s从i-len(word)到i的子串，则将dp[i]设置为True。这表示从字符串开始到当前位置i的子串可以被成功拆分。
- 外层循环
- 返回结果：
return dp[len(s)]：返回dp数组的最后一个元素，即dp[len(s)]。这个值表示整个字符串s是否可以被成功拆分成字典wordDict中的单词。
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False] * (len(s)+1)dp[0] = Truefor i in range(1, len(s)+1):for word in wordDict:if i >= len(word):dp[i] = dp[i] or (dp[i-len(word)] and word == s[i-len(word):i])return dp[len(s)]四、总结篇
关于多重背包，你该了解这些！代码随想录
背包问题总结篇！
代码随想录
