您的位置:首页 > 健康 > 养生 > 辽宁个人网站建设口碑推荐_动画制作app推荐_淘宝流量平台_百度问答我要提问

辽宁个人网站建设口碑推荐_动画制作app推荐_淘宝流量平台_百度问答我要提问

2025/3/16 7:47:41 来源:https://blog.csdn.net/loveJava17/article/details/146277636  浏览:    关键词:辽宁个人网站建设口碑推荐_动画制作app推荐_淘宝流量平台_百度问答我要提问
辽宁个人网站建设口碑推荐_动画制作app推荐_淘宝流量平台_百度问答我要提问

一、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. 代码实现

  1. 初始化动态规划数组 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 表示空字符串可以被成功拆分(因为没有字符需要拆分)。
  2. 动态规划过程
    • 外层循环 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 的子串可以被成功拆分。
  3. 返回结果
    • 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)]

四、总结篇

关于多重背包,你该了解这些!

代码随想录

背包问题总结篇!

代码随想录

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com