一、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)]
四、总结篇
关于多重背包,你该了解这些!代码随想录
背包问题总结篇!
代码随想录