家庭宽带做网站,深圳被点名批评,文库网站开发建设,威海网站开发公司电话1. 背包问题#xff1a;动态规划的“万能钥匙” 很多朋友学动态规划#xff0c;一开始觉得状态转移方程难想#xff0c;后来发现更难的是#xff0c;看到一个题目根本不知道它是不是动态规划#xff0c;更别提怎么套模型了。我刚开始刷LeetCode的时候也是这样#xff0c;…1. 背包问题动态规划的“万能钥匙”很多朋友学动态规划一开始觉得状态转移方程难想后来发现更难的是看到一个题目根本不知道它是不是动态规划更别提怎么套模型了。我刚开始刷LeetCode的时候也是这样看到“目标和”、“零钱兑换”这些题感觉八竿子打不着解法更是五花八门完全摸不着头脑。后来刷多了才发现很多看似复杂的题目背后都藏着一个经典的模型——背包问题。你可以把背包问题想象成动态规划的一个“核心骨架”。就像盖房子骨架搭好了往上填砖瓦就容易多了。背包问题就是这个骨架它提供了一套非常清晰、固定的解题框架给你一堆“物品”数字、硬币、单词一个“背包容量”和、金额、字符串长度问你如何选择物品能在不超过容量的前提下达到某个最优目标能不能装满、最少用几个、有多少种装法。一旦你掌握了这个骨架再去看很多题目就会有一种“哦原来是它”的顿悟感。比如让你给一列数字前面加正负号使得和等于目标值LeetCode 494这怎么是背包呢再比如给你一堆单词问能不能拼成一个长句子LeetCode 139这又跟背包有什么关系别急我们后面会把这些“变装”的题目一件件“扒”回背包的原型。今天我们就用最直白的方式不讲空泛的理论直接通过LeetCode上最经典的几道题把01背包和完全背包这两个核心模型吃透。我会带你一步步拆解从最直观的二维DP表开始到最终刷题必备的一维空间优化把每个易错点、每个“为什么”都讲清楚。目标很简单让你以后在LeetCode上再遇到“选择”和“组合”相关的问题时能第一时间反应过来——“这题能用背包解”。2. 核心理论01背包与完全背包的“灵魂”差异在深入题目之前我们必须把01背包和完全背包最根本的区别刻在脑子里。这个区别直接决定了代码怎么写尤其是那个让人头疼的遍历顺序。2.1 一个故事讲清两种背包想象一下你面前有一排古董每个古董价值不同、重量不同。你有一个承重有限的背包。01背包场景每个古董都是孤品只有一个。你对于每个古董只有两个选择拿1或者不拿0。这就是“01”的由来。比如经典的“分割等和子集”问题数组里的每个数字你只能用它一次要么放进子集A要么放进子集B。完全背包场景每个古董都是无限量供应的仿制品。你可以拿一个拿了之后同样的还可以再拿。比如“零钱兑换”问题硬币面额1元、2元你可以用无数个1元来凑金额。这个“物品能否重复选取”的规则是区分两种背包类型的唯一标准也是所有后续差异的根源。2.2 遍历顺序为什么一个倒序一个正序这是背包问题最核心、也最容易出错的地方。我们直接看一维DP空间优化后的写法这里差异最明显。假设我们用dp[j]表示容量为j的背包能获得的最大价值或方案数等。对于01背包物品不能重复拿for item in items: # 遍历物品 for j in range(capacity, item.weight - 1, -1): # 倒序遍历容量 dp[j] max(dp[j], dp[j - item.weight] item.value)关键点容量j必须从大到小倒序遍历。为什么因为我们需要用“上一轮”的状态来更新当前轮。倒序保证了在计算dp[j]时dp[j - item.weight]还是没有考虑当前物品时的值。如果正序遍历dp[j - item.weight]可能已经被当前物品更新过了这就相当于把同一个物品又装了一次违反了“01”规则。对于完全背包物品可以重复拿for item in items: # 遍历物品 for j in range(item.weight, capacity 1): # 正序遍历容量 dp[j] max(dp[j], dp[j - item.weight] item.value)关键点容量j必须从小到大正序遍历。为什么正序时在计算dp[j]时dp[j - item.weight]已经是考虑过当前物品后的状态了。这意味着我们允许在容量允许的情况下多次装入同一个物品正好符合“完全”背包的要求。你可以这样记01背包怕重复所以要倒着数完全背包欢迎重复所以要正着数。2.3 二维与一维从理解到优化很多教程一上来就讲一维优化我觉得这对新手不太友好。我建议你一定要从二维DP表开始理解。二维DP (dp[i][j])i表示只考虑前i个物品j表示背包容量。状态转移非常直观dp[i][j] max(dp[i-1][j], dp[i-1][j-weight] value)。看它永远只依赖上一行i-1的数据。这完美对应了“每个物品只用一次”。一维DP (dp[j])它其实是把二维表“压扁”了只保留了容量维度。在更新时它滚动覆盖上一轮的数据。正是因为这个“覆盖”操作才产生了上面说的遍历顺序问题。一维DP是空间优化的结果也是面试和刷题时最常用的写法但它的本质必须通过二维来理解。我个人的学习路径是先彻底搞懂二维的填表过程在纸上画几遍直到能闭着眼睛想象出这个表是怎么一步步填满的。然后再去推导为什么二维表可以压缩成一维以及压缩后遍历顺序为什么必须改变。这个过程可能要多花一两个小时但一旦打通后面所有相关的题目都畅通无阻。3. 01背包实战从“能不能”到“有多少种”01背包最常考两类问题可行性判断能不能恰好装满和方案数计算有多少种方法装满。我们通过两道经典题来攻克它。3.1 分割等和子集 (LeetCode 416)经典的“能不能”问题题目给你一个只包含正整数的数组问是否能把这个数组分成两个子集使得两个子集的元素和相等。第一步问题转化识别背包这是最关键的一步也是背包问题的“魔术”所在。如果能分成两个和相等的子集那么数组总和sum必须是偶数。如果是奇数直接返回false。设目标和target sum / 2。转化问题变成了——能否从数组中选出一些数每个数只能用一次使得它们的和恰好等于target。看出来了没物品就是数组中的每个数字背包容量就是target目标是判断能否恰好装满背包布尔值。典型的01背包可行性问题。第二步DP数组定义与初始化我们直接使用最优化的一维DP。dp[j]表示容量为j的背包能否被恰好装满True或False。初始化dp[0] True。容量为0的背包不放任何物品就能“装满”这是所有计算的基准。其他位置初始化为False。第三步状态转移与遍历对于数组中的每个数字num物品我们更新dp数组for num in nums: for j in range(target, num - 1, -1): # 注意倒序遍历 if dp[j - num]: # 如果容量为 j-num 的背包能被装满 dp[j] True # 那么加上当前物品 num容量为 j 的背包也能被装满 # 否则dp[j] 保持原值可能为True或False更简洁的写法是dp[j] dp[j] or dp[j - num]。这里务必用倒序因为每个数字只能用一次。如果正序假设num1dp[1]会被更新为True然后当j2时dp[2] dp[2] or dp[1]这里的dp[1]已经是本轮的True了这意味着我们错误地使用了两次数字1。第四步易错点与实战技巧提前剪枝在遍历前如果发现某个num target说明这个数单独就比目标大永远用不上但注意这不一定导致false其他数可能凑出来。更有效的剪枝是一旦dp[target]在遍历中途变成True就可以立即返回True不用算完了。结果返回最终返回dp[target]即可。我当初踩的坑就是遍历顺序写成了正序在一些特定用例上也能过但逻辑是错误的留下了隐患。所以一定要理解其本质。3.2 目标和 (LeetCode 494)经典的“有多少种”问题题目给你一个整数数组和一个目标数给每个数前面加或-使得表达式结果等于目标数求共有多少种不同的添加符号的方法。第一步问题转化数学推导这道题的转化比上一道更需要技巧。 设所有加的数字和为p所有加-的数字和为sum - p。 我们想要p - (sum - p) target。 解方程2p target sump (target sum) / 2。转化问题变成了——从数组中选出一些数每个数只能用一次使得它们的和恰好等于p问有多少种选法。看物品还是数组中的数字背包容量变成了p但目标变了是求装满背包的方案数。依然是01背包但DP数组的含义和转移方程变了。第二步DP数组定义与初始化dp[j]表示凑出总和恰好为j的方案数。初始化dp[0] 1。凑出总和为0的方案有一种就是一个数都不选。这是方案数问题的基准。第三步状态转移与遍历对于每个数字numfor num in nums: for j in range(p, num - 1, -1): # 同样倒序 dp[j] dp[j - num] # 方案数累加转移方程解释凑成总和j的方案数等于不选当前数num方案数就是原来凑成j的方案数即dp[j]本轮更新前的值。选当前数num方案数就是先凑出j - num然后再放上num的方案数即dp[j - num]。 总的方案数就是这两部分之和。第四步极其重要的边界条件这是本题最大的坑根据公式p (target sum) / 2我们必须保证(target sum)必须是非负偶数否则p不是非负整数直接返回0。p本身必须大于等于0。很多同学写完代码一跑发现结果不对八成是忘了这些判断。我在面试时见过不止一个候选人栽在这里。对比与升华现在我们把这两道01背包问题放在一起看特性分割等和子集 (416)目标和 (494)问题目标布尔值能否装满数值装满的方案数DP定义dp[j]: 能否装满jdp[j]: 装满j的方案数初始化dp[0] Truedp[0] 1状态转移dp[j] dp[j] or dp[j-num]dp[j] dp[j-num]共同核心物品不可重复容量倒序遍历物品不可重复容量倒序遍历看到这个对比你是不是对01背包的“骨架”感觉更清晰了同样的骨架换上不同的“肌肉”DP数组含义和转移方程就能解决不同类型的问题。4. 完全背包实战从“最少用几个”到“能不能拼成”完全背包的经典应用场景更偏向于“无限供给”的组合问题。我们攻克三个最具代表性的题目。4.1 零钱兑换 II (LeetCode 322)最少的硬币个数题目给你不同面额的硬币和一个总金额计算可以凑成总金额所需的最少的硬币个数。每种硬币可以无限使用。第一步问题转化这几乎是完全背包的“标准自我介绍”。物品硬币面额。容量总金额。目标求装满背包所需的最少物品数量。特性物品无限取用 - 完全背包。第二步DP定义与初始化dp[j]凑成总金额j所需的最少硬币个数。初始化dp[0] 0。凑出金额0需要0个硬币。其他位置dp[j]初始化为一个“最大值”比如amount 1或float(inf)表示暂时无法凑出。第三步状态转移与遍历for coin in coins: # 遍历物品硬币 for j in range(coin, amount 1): # 正序遍历容量 dp[j] min(dp[j], dp[j - coin] 1)解释对于当前金额j我们可以选择不使用当前硬币coin方案数为dp[j]或者使用至少一枚当前硬币方案数为dp[j - coin] 1。取两者的最小值。注意这里是正序因为硬币可以无限使用我们希望dp[j - coin]是已经考虑过使用当前硬币后的最优解。第四步结果与易错点最终结果如果dp[amount]仍然是初始化的那个最大值说明凑不出返回-1否则返回dp[amount]。易错点初始化值不能是float(inf)之类的因为在dp[j - coin] 1时可能导致整数溢出。用amount 1是更安全的选择因为最多的情况就是用amount个1元硬币。4.2 完全平方数 (LeetCode 279)最少的平方数个数题目给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。第一步问题转化这道题是“零钱兑换”的变体甚至更简单。物品所有小于等于n的完全平方数1, 4, 9, ...。容量n。目标求装满背包所需的最少物品数量。特性每个平方数可以无限使用 - 完全背包。第二步DP定义与实现实现和零钱兑换几乎一模一样dp [float(inf)] * (n 1) dp[0] 0 # 生成物品列表完全平方数 squares [i*i for i in range(1, int(n**0.5)1)] for square in squares: for j in range(square, n 1): dp[j] min(dp[j], dp[j - square] 1) return dp[n]一个思维陷阱有人会想用贪心每次选最大的平方数。比如n12先选9剩下3需要三个1总共4个。但最优解是444只需要3个。这再次证明了动态规划“全局考虑”的优势。4.3 单词拆分 (LeetCode 139)布尔值的完全背包题目给你一个字符串 s 和一个字符串列表 wordDict判断 s 是否可以被空格拆分成一个或多个在字典中出现的单词。字典中的单词可以重复使用。第一步问题转化需要一些跳跃这道题不像前两道那么直观。我们需要换个角度看容量字符串s的长度n。物品字典wordDict中的每个单词。目标判断能否用这些单词物品恰好拼出长度为n的字符串装满背包。特性单词可以重复使用 - 完全背包。但这里有个关键背包的“容量”是长度而“物品”不仅有“重量”单词长度还有其“内容”必须和字符串的对应部分匹配。第二步DP定义dp[i]表示字符串s的前i个字符即s[0:i]能否被成功拆分。初始化dp[0] True。空字符串可以被认为是可以拆分的即不选任何单词。第三步状态转移这是最精妙的部分。我们遍历“容量”i从1到n对于每个容量我们遍历所有“物品”单词n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): # i是当前考虑的字符串长度背包容量 for word in wordDict: # 遍历每个单词物品 word_len len(word) if i word_len and dp[i - word_len]: # 容量够且减去单词长度后的状态为True if s[i - word_len : i] word: # 并且当前子串匹配这个单词 dp[i] True break # 找到一个能拆分的单词就可以跳出内层循环 return dp[n]解释dp[i]为True的条件是存在一个单词word使得这个单词的长度word_len小于等于当前长度i。字符串s从i-word_len到i的这个子串正好等于word。并且在去掉这个单词之后剩下的前i-word_len个字符也是可拆分的即dp[i - word_len]为True。第四步优化与技巧遍历顺序这里我们是先遍历容量i再遍历物品word。对于完全背包求布尔值的情况遍历顺序先物品还是先容量有时可以互换但这里先容量更符合逻辑因为我们是以字符串的每个结束位置为切入点进行判断。提前结束内层循环中一旦发现dp[i]为True就可以break因为我们已经找到了一个拆分方式无需再检查其他单词。使用集合将wordDict转换为集合set可以使in操作更快但这里我们主要需要遍历和比较长度所以转换集合对匹配子串的帮助有限主要优化在于去重。这道题成功地将字符串匹配问题“塞”进了背包模型是检验你是否真正理解背包问题“抽象”能力的绝佳例题。5. 融会贯通构建你的解题框架刷了这么多题是时候把散落的知识点串成线织成网了。下面这个框架是我自己用了很久的每次遇到新题就往里套百试不爽。第一步识别背包类型30%的功力问自己在这个问题里所谓的“物品”是只能用一次还是无限次使用只能用一次-01背包。典型信号数组中的每个元素只能被选择一次选或不选。无限次使用-完全背包。典型信号硬币、平方数、单词可重复使用。第二步抽象三要素50%的功力这是最关键的一步决定了你能不能把实际问题转化成背包模型。容量 (Capacity)背包最多能装多少通常是题目中要凑的那个目标值和、金额、长度。物品 (Items)每个物品的“价值”和“重量”是什么在方案数问题里“价值”可能就是1表示一种选择在最少个数问题里“价值”可能就是物品本身在布尔值问题里可能没有显式价值。目标 (Goal)是求最大/最小值还是方案数还是可行性第三步定义DP数组并初始化10%的功力根据目标来定义求最值dp[j] min(dp[j], dp[j-cost] value)或max(...)。初始化时dp[0]通常为0基准其他位置为极大或极小值。求方案数dp[j] dp[j-cost]。初始化dp[0] 1。求可行性dp[j] dp[j] or dp[j-cost]。初始化dp[0] True。第四步确定遍历顺序并实现10%的功力01背包一维DP先遍历物品再倒序遍历容量。完全背包一维DP先遍历物品再正序遍历容量求组合数有时求排列数时顺序有影响但大多数情况下先物品后容量正序即可。特殊情况像“单词拆分”这种先遍历容量再遍历物品可能更自然。最后也是最重要的思维动态规划尤其是背包问题练的是一种“转化”的思维。LeetCode不会把“背包”两个字写在题目里。它可能叫“分割等和子集”可能叫“目标和”可能叫“零钱兑换”。你的任务就是拨开这些描述的外衣看到里面“选择物品-满足容量-达到目标”的骨架。我建议你拿出一个笔记本专门记录这种“转化”案例。左边写题目描述和关键约束右边写你分析出的背包模型物品、容量、目标、类型。积累十几个这样的案例后你会发现再看到新题你的第一反应不再是“这题怎么做”而是“这题像哪个背包模型”。到了这个阶段动态规划对你来说就不再是玄学而是一套可重复、可套用的强大工具了。