1. 经典动态规划第二篇从会套模板到真懂状态如果你一路刷题刷到这里大概率已经被背包问题折磨过几轮了。这个系列上一篇我们聊了动态规划的基础框架——斐波那契、爬楼梯、打家劫舍这类入门题这些题的核心套路是前i个位置怎么递推状态只有一维转移方程基本一眼能看穿。但到了面试常考题的进阶阶段动态规划的难度会上一个台阶最大的变化就是状态从一个维度变成两个维度决策从取或不取变成取几个。这篇文章聚焦的是面试中出现频率最高的动态规划进阶类型——背包问题家族。我先说个面试时的真实观察很多候选人刷过背包九讲能背出01背包的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])但被问到为什么一维数组要倒序遍历的时候直接卡住。面试官其实很看重这一点因为倒序遍历不是背下来的规则而是状态定义本身逻辑推导出来的必然结果。所以这篇文章不会只给你模板我会把每个关键选择的为什么拆开揉碎讲清楚。这篇文章适合谁看正在准备算法面试、刷LeetCode和牛客的求职者尤其是那些已经刷完入门DP题、但对背包类问题还是似懂非懂的人。看完你会搞明白三件事01背包一维优化的原理、完全背包和多重背包的代码差异点、以及面试中如何快速拆解背包变种题。2. 动态规划的思维底子状态定义决定一切2.1 从暴力枚举到填表的思维转换在讲背包问题之前我必须先把动态规划的核心思维方式再压一遍。很多人在做DP题的时候习惯去背模板但模板只能帮你对付原题面试官稍微改一个限制条件你就懵了。真正的思考路径应该是从暴力解出发一步步推导出DP解。拿01背包举例题目描述是有n个物品每个物品有重量w[i]和价值v[i]背包容量为C每个物品只能取一次0次或1次问能装入背包的最大总价值是多少。如果暴力枚举每个物品有取和不取两种状态n个物品就是2^n种组合你逐个计算所有组合的总重量和总价值筛掉超重的取最大价值。这个思路本身没错但n到30就已经跑不动了。怎么优化观察暴力枚举的过程你会发现大量子问题是重复计算的——比如枚举完前5个物品的装法后第6到第n个物品的决策完全不依赖前5个具体怎么装的只依赖当前已经占用了多少容量。这就是动态规划的切入点把决策到第几个物品和当前剩余容量这两个要素从暴力枚举中抽出来作为状态的两个维度然后用填表的方式避免重复计算。理解了这个思路你就明白为什么背包问题的状态是二维的——它本质上是在记录暴力搜索过程中每个中间节点的最优值只是用表的方式存了下来。2.2 四个要素状态、转移、初始化、遍历顺序很多教程讲DP喜欢直接给状态转移方程然后甩一段代码。但我的经验是一个DP解法真正难的不是方程本身而是四个要素彼此咬合的关系。我面试别人时喜欢按这个顺序提问状态定义是什么转移方程怎么来的初始化为什么是这个值遍历顺序能不能换这四个要素的优先级是自上而下的。状态定义错了后面全是错的状态定义对了转移方程就是当前状态从哪些前置状态来的枚举初始化是边界条件的落地遍历顺序是代码实现时保证转移方程用到的值已经被算好的手段。很多人在遍历顺序上翻车根本原因是没想清楚转移方程依赖的格子在当前遍历到的时候是不是已经填好了。这个框架不仅能用在背包问题上任何DP题都可以套。你拿到一道题先想状态的两个维度分别代表什么再想当前状态可能从哪些状态转移过来然后处理边界最后选遍历方向。这篇文章后面所有的题目拆解都会围绕这四个要素展开。3. 01背包全拆解面试最高频的DP模型3.1 二维DP版本先解决对不对第一步永远是先把正确的解法写出来不要一上来就优化。01背包的二维DP版本状态定义和转移方程如下dp[i][j]考虑前i个物品下标从1到i在背包容量为j时的最大总价值状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])第一个选项dp[i-1][j]表示不取第i个物品那结果就等于前i-1个物品在容量j下的最优解第二个选项dp[i-1][j-w[i]] v[i]表示取第i个物品那要先把容量j中腾出w[i]的空间给第i个物品前i-1个物品只能使用剩下j-w[i]的容量再加上第i个物品的价值。这个转移方程怎么来的用我前面说的思路就是在枚举第i个物品的决策取带来什么后果不取带来什么后果两者取最大值。枚举完一个物品后面的物品决策就不依赖前面具体选了哪些只依赖剩余容量。这就是无后效性DP能成立的前提。代码写出来大概是这样的我用Python因为面试写起来快、可读性好def knapsack_01_2d(n, C, w, v): # dp[i][j]: 前i个物品容量为j的最大价值 dp [[0] * (C 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(0, C 1): # 不取第i个物品 dp[i][j] dp[i-1][j] # 取第i个物品前提是容量够 if j w[i-1]: dp[i][j] max(dp[i][j], dp[i-1][j-w[i-1]] v[i-1]) return dp[n][C]注意初始化二维数组的dp[0][j]也就是前0个物品无论容量多少最大价值都是0。这个初始化是没有物品可选时价值为0的直观表达。所有行滚动更新时天然从第i-1行推到第i行不会出现覆盖还没用的格子的问题。3.2 一维滚动数组为什么必须倒序遍历二维版本解决了问题但空间复杂度是O(n*C)。面试官大概率会追问一句能优化空间吗这时候就要上滚动数组。观察二维版本的转移方程dp[i][j]只依赖dp[i-1][...]这一行也就是说第i-1行之前的数据在算第i行时完全用不到那我们就没必要保留整张表用一个一维数组反复覆盖更新即可。核心代码如下def knapsack_01_1d(n, C, w, v): dp [0] * (C 1) for i in range(1, n 1): # 关键容量从大到小遍历 for j in range(C, w[i-1] - 1, -1): dp[j] max(dp[j], dp[j - w[i-1]] v[i-1]) return dp[C]这里最关键、面试必问的一点为什么内层循环要从C倒序遍历到w[i]答案是因为一维数组在更新dp[j]的时候dp[j]本身代表的是前i-1个物品在容量j下的最优值而dp[j-w[i]]需要也是前i-1个物品的最优值。如果正序遍历dp[j-w[i]]可能已经被当前第i个物品更新过了那就变成了同一个物品被取多次——这恰好是后面要讲的完全背包的逻辑。举个例子就明白了。假设背包容量C5当前物品重量w2价值v3。正序遍历先更新dp[2] max(dp[2], dp[0] 3) 3然后更新dp[4] max(dp[4], dp[2] 3)。问题出现了这个dp[2]是刚被当前物品更新过的值它里面可能已经包含了当前物品于是dp[4]就可能等于当前物品取了两次的价值先占2容量再占2容量价值加了两次。可01背包每个物品只能取一次这显然不对。倒序遍历先更新dp[5]此时用到的dp[3]是上一轮前i-1个物品的旧值没被污染然后更新dp[4]用到的dp[2]也是旧值最后更新dp[2]。这样每个物品只被考虑一次完美符合01背包的语义。注意面试时如果被问到二维转一维除了空间优化还有什么好处可以从代码简洁性和面试表达两个角度回答。但不要画蛇添足说时间也优化了——时间复杂度没有变化仍然是O(n*C)。3.3 一个容易忽略的细节物品和容量的遍历顺序01背包还有个容易被忽视的细节外层循环是物品内层是容量那能不能交换两层循环的顺序我直接说结论在01背包中如果用了二维DP交换两层循环的顺序通常也能得到正确结果只是语义上别扭但用了一维滚动数组优化后外层遍历物品、内层倒序遍历容量这个顺序是不能随便交换的。因为外循环每轮只引入一个物品内层倒序遍历保证了这一轮更新不会影响本轮的其他更新前面说过的污染问题。如果两层循环交换外循环变容量、内循环遍历物品那么同一个容量下会同时考虑多个物品加入直接破坏每个物品最多取一次的限制。所以你在面试时可以说一维优化版的01背包物品循环必须在外面容量循环必须在里面且倒序。这个回答既展示了编码熟练度也体现了对循环语义的理解。4. 完全背包和多重背包背包家族的三兄弟对比4.1 完全背包物品可以取无限次完全背包和01背包唯一的区别是每个物品可以取无限次只要容量装得下。这个差异看起来很小但对代码的影响是颠覆性的。先说二维DP推导。完全背包的状态定义和01背包一样dp[i][j]表示前i个物品在容量j下的最大价值。但状态转移方程发生了变化因为第i个物品可以取多次所以当前状态不只是不取第i个或取1个第i个两种选择而是取k个第i个k可以从0取到j//w[i]。暴力写法是枚举kdp[i][j] max(dp[i-1][j], max_{k1, k*w[i]j}(dp[i-1][j-k*w[i]] k*v[i]))但这个枚举k的复杂度是O(nCC)太慢了。优化思路是用递推关系消掉枚举。观察发现dp[i][j]取第i个物品的话等价于dp[i][j-w[i]] v[i]。为什么因为取1个第i个物品之后你面对的还是前i个物品、容量j-w[i]的子问题第i个物品还能继续取这就是无限次取同一个物品的核心语义。于是转移方程简化为dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])这里要注意第二个选项dp[i][j-w[i]]用的是同一行的格子也就是在容量更小的时候已经考虑过继续取第i个物品的情况了这和01背包用dp[i-1][j-w[i]]完全不同。再转成一维数组你会看到神奇的事情完全背包的内层循环恰好是正序的def knapsack_complete(n, C, w, v): dp [0] * (C 1) for i in range(1, n 1): for j in range(w[i-1], C 1): # 正序遍历 dp[j] max(dp[j], dp[j - w[i-1]] v[i-1]) return dp[C]为什么正序就对了因为正序遍历的时候dp[j-w[i]]可能已经包含当前物品所以dp[j]可以往多次取当前物品的方向更新。这和01背包的倒序刚好相反。面试时如果能把01倒序、完全正序这个差异背后的原理讲清楚面试官基本就认定你真的懂DP了而不是背代码。4.2 多重背包物品有次数限制怎么把复杂度降下来多重背包是这么个问题第i个物品最多能用c[i]次问最大价值。它介于01背包只能用1次和完全背包无限次之间。最直接的做法是枚举每个物品取了多少个转移方程变成dp[i][j] max(dp[i-1][j - k*w[i]] k*v[i])其中0 k c[i]且k*w[i] j。复杂度O(nCC)严格说是O(nC平均c[i])在面试题里基本会超时需要优化。多重背包最常用的优化是二进制拆分。核心思想一个物品的c[i]个可用次数可以拆成若干个01背包物品每个拆分出来的物品重量是w[i] * (2^k)价值是v[i] * (2^k)把所有拆分后的新物品跑一遍01背包即可。为什么是2的幂因为[1,2,4,...,剩余]这个组合能表示0到c[i]之间的任意整数这是二进制表示的基本原理。举个例子如果c[i]10可以拆成1、2、4、310-1-2-43四个新物品这四个数任意组合能覆盖0到10的所有整数。代码实现如下def knapsack_multiple(n, C, w, v, c): new_w, new_v [], [] for i in range(n): # 二进制拆分 k 1 while k c[i]: new_w.append(w[i] * k) new_v.append(v[i] * k) c[i] - k k 1 if c[i] 0: new_w.append(w[i] * c[i]) new_v.append(v[i] * c[i]) # 01背包跑一遍 dp [0] * (C 1) for i in range(len(new_w)): for j in range(C, new_w[i] - 1, -1): dp[j] max(dp[j], dp[j - new_w[i]] new_v[i]) return dp[C]我来解释一下这段代码里几个值得注意的点while k c[i]从1开始不断乘2直到超过剩余次数。每次拆分出一个重量为w[i]*k、价值为v[i]*k的新物品。最后if c[i] 0处理剩余次数比如10拆完1、2、4后还剩3就拆一个3个一起的组。这3个一组要和1、2、4组合起来恰好覆盖到10。拆分完成后新物品的取或不取本质上就是在决定原始物品取k个这个决策所以直接套01背包的模板就行。注意二进制拆分后物品数量从n变成了O(nlog(max(c)))级别所以整体复杂度是O(n * log(c) * C)。这个优化在面试中属于进阶考点如果面试官没主动问可以在写完基础多重背包解法后主动提一句如果用二进制拆分可以优化到O(nlog(c)*C)会加分不少。4.3 三兄弟对比速查表为了方便记忆和快速查阅我把三种背包的核心差异整理成一张表问题类型物品可用次数一维遍历顺序转移方程一维典型复杂度01背包最多1次倒序dp[j] max(dp[j], dp[j-w]v)O(n*C)完全背包无限次正序dp[j] max(dp[j], dp[j-w]v)O(n*C)多重背包最多c[i]次拆分后按01背包先拆分再走01背包O(n*log(c)*C)这张表最底层的规律是遍历顺序不是拍脑袋定的而是由转移方程依赖上一行还是同一行的值决定的。01背包转移依赖dp[j-w]里不含当前物品的最优值所以要保证它不被当前更新污染——倒序完全背包转移依赖dp[j-w]里已包含当前物品的最优值所以要用当前更新的结果——正序。把这个逻辑讲清楚遍历顺序就不会记反。5. 从经典模板到高频变种面试题真正考你的地方5.1 恰好装满初始化方式的微调背包问题最常见的一个变种是要求恰好装满背包而不是不超过容量。比如LeetCode 322题零钱兑换问凑出amount金额需要的最少硬币数LeetCode 416题分割等和子集问能否选出若干数恰好等于总和的一半。这类题和标准背包的差别在初始化上这一点很多人踩坑。回顾标准背包我们初始化所有dp[j] 0含义是容量j下可以不装任何东西价值为0。但恰好装满的语义下容量为0时恰好装满的方案是存在的什么都不选价值为0但容量大于0时如果没有合法方案应该初始化为负无穷求最大值时或正无穷求最小值时表示目前无法恰好凑满。拿LeetCode 322举例子dp[j]表示凑出金额j所需的最少硬币数。初始化dp[0]0其他dp[j]float(inf)。这样在状态转移时dp[j] min(dp[j], dp[j-coin] 1)只有当dp[j-coin]不是无穷大时dp[j]才能被更新为有效值。如果没有这个初始化dp[5]可能被错误地更新成inf1之类的垃圾值。用暴力枚举类比你枚举所有可能凑出金额j的组合如果凑不出来结果应该是不存在而不是凑了0个硬币。初始化就是提前告诉DP表除容量0外其他容量目前都凑不满。注意我见过候选人写恰好装满的题时代码逻辑全对就是初始化的正负无穷设置错了方向。求最小值用float(inf)求最大值用float(-inf)这个别看反了。5.2 求方案数加号变求和另一个高频变种是求方案数。比如LeetCode 494题目标和给你一个数组每个数前面可以加正号或负号问有多少种方法让最终结果等于target。如果你被背包的最大价值思维定式锁住可能半天想不出来。但实际上这类题只是把转移方程里的max换成而已。具体来说定义dp[j]表示凑出数值j的方法数那么状态转移就是dp[j] dp[j - num]。含义是当前数取正的话要凑出j前面得先凑出j-num方案数是dp[j-num]当前数取负的话前面得先凑出jnum方案数是dp[jnum]。这里要注意的是遍历顺序和初始化初始化dp[0]1因为凑出0只有一种方法——什么都不选。做完状态转移后答案就是dp[target]可能需要处理偏移量因为负数下标不支持。这类题目只要识别出计数两个字就不应该继续套max/min模板而是换成累加。5.3 二维费用背包状态多一个维度还有一种变种是二维费用背包背包限重的同时限体积。比如LeetCode 474题一和零给你若干字符串每个字符串里有若干个0和1问在最多能用m个0和n个1的限制下最多能选多少个字符串。这类题的状态要从二维变成三维dp[i][j][k]表示前i个物品在0的容量为j、1的容量为k时的最大选择数。通常可以压缩成二维滚动数组dp[j][k]外层遍历物品内层两个容量维度都要倒序遍历因为压缩后要用旧值。转移方程就是01背包的二维版for s in strs: zeros s.count(0) ones len(s) - zeros for j in range(m, zeros - 1, -1): for k in range(n, ones - 1, -1): dp[j][k] max(dp[j][k], dp[j - zeros][k - ones] 1)面试中遇到二维费用的变种判断标准很简单题目里同时出现两个独立限制条件比如重量体积、0的数量1的数量转移时就需要两个维度同时参与。5.4 背包装物品还是装字数识别变种的换皮套路我来总结一个判断变种题型的方法面试题经常把背包装进各种故事里但底层状态定义万变不离其宗。怎么快速识别看三个点题目问的是最大价值/最小代价还是方案数——max/min还是求和每个物品/元素能不能重复用——决定01背包还是完全背包有没有恰好的约束——决定初始化的正负无穷举个例子LeetCode 139题单词拆分给定一个字符串s和一个单词字典wordDict问s能否拆分成若干个字典里的单词。看起来和背包八竿子打不着但你可以把s[0:i]能否拆分看作状态dp[i]从位置j切一刀如果dp[j]为真且s[j:i]在字典里那dp[i]就为真。这本质上就是一个每个单词可以用无限次的完全背包求可行性问题。识别出这个对应关系代码就很好写了。6. 面试实战拿到DP题的10分钟思考顺序6.1 从记忆化搜索到DP先写暴力递归再优化面试过程中很多人容易犯的毛病是拿到题目直接开始写状态转移方程结果卡在定义上越写越乱。我建议的流程是前2-3分钟先用暴力递归的思维把问题描述清楚。比如01背包暴力递归其实就是def dfs(i, rest_capacity): if i n: return 0 # 不取第i个 res dfs(i 1, rest_capacity) # 取第i个如果放得下 if rest_capacity w[i]: res max(res, dfs(i 1, rest_capacity - w[i]) v[i]) return res然后你观察这个递归函数它有i和rest_capacity两个参数这说明状态有两个维度。再用一个memo缓存计算结果就变成了记忆化搜索。最后把递归改成循环填表就得到了标准的DP解法。这个过程其实是在帮你理清状态定义和转移逻辑比硬想方程要容易得多。面试时我强烈建议你把这个推理路径说给面试官听先写递归再指出重复子问题再加备忘录再转递推。这个过程本身就展示了你的问题拆解能力比直接甩dp[i][j]的公式令人信服得多。6.2 边界条件检查的三个固定步骤写完DP代码之后不要急着说做完了。花10秒钟做三件事检查数组长度dp数组的长度是C1还是C有没有越界风险检查初始化的语义容量0的值是不是符合题目要求不等价于0的情况恰好装满、最小值有没有特殊处理检查遍历方向内层循环是正序还是倒序有没有可能覆盖还没用的旧值这三个步骤能挡住大部分运行时错误。我见过不少人栽在数组初始化长度为C但访问了dp[C]这种低级错误上面试时这种错误比算法不会更扣分因为它说明你平时写代码不够细心。6.3 空间优化的分寸感不要一上来就写一维我在面试中观察到一个很有意思的现象候选人写01背包一上来就写一维滚动数组的版本。代码确实没问题但面试官追问为什么倒序时答不上来。这有点像背题。我的建议是如果面试官没有明确要求优化空间你可以先写二维版本讲清楚状态定义和转移逻辑然后主动说这个版本空间复杂度是O(n*C)我可以优化成O(C)。这样展示了两层能力能写出正确解也懂优化。反过来如果先写一维被追问的时候紧张了容易露怯。当然如果题目本身的数据范围很大比如C到10^6二维数组根本开不下就直接写一维同时解释为什么可以滚动更新。6.4 被追问能再优化吗时的三种思路面试官经常在常规解法之后追问还有其他优化吗这个时候可以从三个角度思考时间优化能否减少状态维度能否用单调队列优化多重背包这个比较深一般不问空间优化滚动数组、原地更新、用short类型存值等剪枝优化物品按性价比排序用上界剪枝这偏向搜索DP题较少用其中空间优化是最高频的追问方向其次是如果物品数量很大但容量很小怎么办这种问题——答案是把思路反过来容量维度小就用容量做状态物品多没关系。7. 给刷题人的三个实测建议文章最后这个部分我想分享几个自己刷题和面试过程中的实际体会不展开成章节了就写最实用的三条。第一条背包问题的代码量其实很少难的是识别和变通。我建议你把这篇文章里的三类背包模板01、完全、多重自己手写三遍每次写都先口述一遍为什么倒序/正序/二进制拆分再动笔。这样练下来的效果比刷十道同类型题都好。第二条刷动态规划题的时候建议专门用一个笔记记录每道题的状态定义转移方程初始化不用写完整代码。面试前翻一翻笔记比重新刷一遍题高效得多。动笔写的过程本身会逼迫你理清思路这是纯看题解学不到的。第三条也是最重要的一条面试时如果卡住了不要慌试着用暴力递归开始讲思路。面试官要看的不是你一次写对而是你在不知道正解时的思考路径。动态规划这个题型尤其如此很多候选人是会做的都会稍微变形就废本质原因就是没有从暴力递归的底层逻辑去理解状态定义。从递归到DP这个推导链是你面试复习中最值得花时间的部分。背包问题这块内容基本就是这些了下一篇系列里我打算聊一聊区间DP和树形DP这两个方向在面试中也经常出现而且思维方式和背包类问题又不一样到时候再把我踩过的坑和总结的技巧一并分享出来。 动态规划背包问题全解析：从01背包到多重背包
1. 经典动态规划第二篇从会套模板到真懂状态如果你一路刷题刷到这里大概率已经被背包问题折磨过几轮了。这个系列上一篇我们聊了动态规划的基础框架——斐波那契、爬楼梯、打家劫舍这类入门题这些题的核心套路是前i个位置怎么递推状态只有一维转移方程基本一眼能看穿。但到了面试常考题的进阶阶段动态规划的难度会上一个台阶最大的变化就是状态从一个维度变成两个维度决策从取或不取变成取几个。这篇文章聚焦的是面试中出现频率最高的动态规划进阶类型——背包问题家族。我先说个面试时的真实观察很多候选人刷过背包九讲能背出01背包的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])但被问到为什么一维数组要倒序遍历的时候直接卡住。面试官其实很看重这一点因为倒序遍历不是背下来的规则而是状态定义本身逻辑推导出来的必然结果。所以这篇文章不会只给你模板我会把每个关键选择的为什么拆开揉碎讲清楚。这篇文章适合谁看正在准备算法面试、刷LeetCode和牛客的求职者尤其是那些已经刷完入门DP题、但对背包类问题还是似懂非懂的人。看完你会搞明白三件事01背包一维优化的原理、完全背包和多重背包的代码差异点、以及面试中如何快速拆解背包变种题。2. 动态规划的思维底子状态定义决定一切2.1 从暴力枚举到填表的思维转换在讲背包问题之前我必须先把动态规划的核心思维方式再压一遍。很多人在做DP题的时候习惯去背模板但模板只能帮你对付原题面试官稍微改一个限制条件你就懵了。真正的思考路径应该是从暴力解出发一步步推导出DP解。拿01背包举例题目描述是有n个物品每个物品有重量w[i]和价值v[i]背包容量为C每个物品只能取一次0次或1次问能装入背包的最大总价值是多少。如果暴力枚举每个物品有取和不取两种状态n个物品就是2^n种组合你逐个计算所有组合的总重量和总价值筛掉超重的取最大价值。这个思路本身没错但n到30就已经跑不动了。怎么优化观察暴力枚举的过程你会发现大量子问题是重复计算的——比如枚举完前5个物品的装法后第6到第n个物品的决策完全不依赖前5个具体怎么装的只依赖当前已经占用了多少容量。这就是动态规划的切入点把决策到第几个物品和当前剩余容量这两个要素从暴力枚举中抽出来作为状态的两个维度然后用填表的方式避免重复计算。理解了这个思路你就明白为什么背包问题的状态是二维的——它本质上是在记录暴力搜索过程中每个中间节点的最优值只是用表的方式存了下来。2.2 四个要素状态、转移、初始化、遍历顺序很多教程讲DP喜欢直接给状态转移方程然后甩一段代码。但我的经验是一个DP解法真正难的不是方程本身而是四个要素彼此咬合的关系。我面试别人时喜欢按这个顺序提问状态定义是什么转移方程怎么来的初始化为什么是这个值遍历顺序能不能换这四个要素的优先级是自上而下的。状态定义错了后面全是错的状态定义对了转移方程就是当前状态从哪些前置状态来的枚举初始化是边界条件的落地遍历顺序是代码实现时保证转移方程用到的值已经被算好的手段。很多人在遍历顺序上翻车根本原因是没想清楚转移方程依赖的格子在当前遍历到的时候是不是已经填好了。这个框架不仅能用在背包问题上任何DP题都可以套。你拿到一道题先想状态的两个维度分别代表什么再想当前状态可能从哪些状态转移过来然后处理边界最后选遍历方向。这篇文章后面所有的题目拆解都会围绕这四个要素展开。3. 01背包全拆解面试最高频的DP模型3.1 二维DP版本先解决对不对第一步永远是先把正确的解法写出来不要一上来就优化。01背包的二维DP版本状态定义和转移方程如下dp[i][j]考虑前i个物品下标从1到i在背包容量为j时的最大总价值状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])第一个选项dp[i-1][j]表示不取第i个物品那结果就等于前i-1个物品在容量j下的最优解第二个选项dp[i-1][j-w[i]] v[i]表示取第i个物品那要先把容量j中腾出w[i]的空间给第i个物品前i-1个物品只能使用剩下j-w[i]的容量再加上第i个物品的价值。这个转移方程怎么来的用我前面说的思路就是在枚举第i个物品的决策取带来什么后果不取带来什么后果两者取最大值。枚举完一个物品后面的物品决策就不依赖前面具体选了哪些只依赖剩余容量。这就是无后效性DP能成立的前提。代码写出来大概是这样的我用Python因为面试写起来快、可读性好def knapsack_01_2d(n, C, w, v): # dp[i][j]: 前i个物品容量为j的最大价值 dp [[0] * (C 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(0, C 1): # 不取第i个物品 dp[i][j] dp[i-1][j] # 取第i个物品前提是容量够 if j w[i-1]: dp[i][j] max(dp[i][j], dp[i-1][j-w[i-1]] v[i-1]) return dp[n][C]注意初始化二维数组的dp[0][j]也就是前0个物品无论容量多少最大价值都是0。这个初始化是没有物品可选时价值为0的直观表达。所有行滚动更新时天然从第i-1行推到第i行不会出现覆盖还没用的格子的问题。3.2 一维滚动数组为什么必须倒序遍历二维版本解决了问题但空间复杂度是O(n*C)。面试官大概率会追问一句能优化空间吗这时候就要上滚动数组。观察二维版本的转移方程dp[i][j]只依赖dp[i-1][...]这一行也就是说第i-1行之前的数据在算第i行时完全用不到那我们就没必要保留整张表用一个一维数组反复覆盖更新即可。核心代码如下def knapsack_01_1d(n, C, w, v): dp [0] * (C 1) for i in range(1, n 1): # 关键容量从大到小遍历 for j in range(C, w[i-1] - 1, -1): dp[j] max(dp[j], dp[j - w[i-1]] v[i-1]) return dp[C]这里最关键、面试必问的一点为什么内层循环要从C倒序遍历到w[i]答案是因为一维数组在更新dp[j]的时候dp[j]本身代表的是前i-1个物品在容量j下的最优值而dp[j-w[i]]需要也是前i-1个物品的最优值。如果正序遍历dp[j-w[i]]可能已经被当前第i个物品更新过了那就变成了同一个物品被取多次——这恰好是后面要讲的完全背包的逻辑。举个例子就明白了。假设背包容量C5当前物品重量w2价值v3。正序遍历先更新dp[2] max(dp[2], dp[0] 3) 3然后更新dp[4] max(dp[4], dp[2] 3)。问题出现了这个dp[2]是刚被当前物品更新过的值它里面可能已经包含了当前物品于是dp[4]就可能等于当前物品取了两次的价值先占2容量再占2容量价值加了两次。可01背包每个物品只能取一次这显然不对。倒序遍历先更新dp[5]此时用到的dp[3]是上一轮前i-1个物品的旧值没被污染然后更新dp[4]用到的dp[2]也是旧值最后更新dp[2]。这样每个物品只被考虑一次完美符合01背包的语义。注意面试时如果被问到二维转一维除了空间优化还有什么好处可以从代码简洁性和面试表达两个角度回答。但不要画蛇添足说时间也优化了——时间复杂度没有变化仍然是O(n*C)。3.3 一个容易忽略的细节物品和容量的遍历顺序01背包还有个容易被忽视的细节外层循环是物品内层是容量那能不能交换两层循环的顺序我直接说结论在01背包中如果用了二维DP交换两层循环的顺序通常也能得到正确结果只是语义上别扭但用了一维滚动数组优化后外层遍历物品、内层倒序遍历容量这个顺序是不能随便交换的。因为外循环每轮只引入一个物品内层倒序遍历保证了这一轮更新不会影响本轮的其他更新前面说过的污染问题。如果两层循环交换外循环变容量、内循环遍历物品那么同一个容量下会同时考虑多个物品加入直接破坏每个物品最多取一次的限制。所以你在面试时可以说一维优化版的01背包物品循环必须在外面容量循环必须在里面且倒序。这个回答既展示了编码熟练度也体现了对循环语义的理解。4. 完全背包和多重背包背包家族的三兄弟对比4.1 完全背包物品可以取无限次完全背包和01背包唯一的区别是每个物品可以取无限次只要容量装得下。这个差异看起来很小但对代码的影响是颠覆性的。先说二维DP推导。完全背包的状态定义和01背包一样dp[i][j]表示前i个物品在容量j下的最大价值。但状态转移方程发生了变化因为第i个物品可以取多次所以当前状态不只是不取第i个或取1个第i个两种选择而是取k个第i个k可以从0取到j//w[i]。暴力写法是枚举kdp[i][j] max(dp[i-1][j], max_{k1, k*w[i]j}(dp[i-1][j-k*w[i]] k*v[i]))但这个枚举k的复杂度是O(nCC)太慢了。优化思路是用递推关系消掉枚举。观察发现dp[i][j]取第i个物品的话等价于dp[i][j-w[i]] v[i]。为什么因为取1个第i个物品之后你面对的还是前i个物品、容量j-w[i]的子问题第i个物品还能继续取这就是无限次取同一个物品的核心语义。于是转移方程简化为dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])这里要注意第二个选项dp[i][j-w[i]]用的是同一行的格子也就是在容量更小的时候已经考虑过继续取第i个物品的情况了这和01背包用dp[i-1][j-w[i]]完全不同。再转成一维数组你会看到神奇的事情完全背包的内层循环恰好是正序的def knapsack_complete(n, C, w, v): dp [0] * (C 1) for i in range(1, n 1): for j in range(w[i-1], C 1): # 正序遍历 dp[j] max(dp[j], dp[j - w[i-1]] v[i-1]) return dp[C]为什么正序就对了因为正序遍历的时候dp[j-w[i]]可能已经包含当前物品所以dp[j]可以往多次取当前物品的方向更新。这和01背包的倒序刚好相反。面试时如果能把01倒序、完全正序这个差异背后的原理讲清楚面试官基本就认定你真的懂DP了而不是背代码。4.2 多重背包物品有次数限制怎么把复杂度降下来多重背包是这么个问题第i个物品最多能用c[i]次问最大价值。它介于01背包只能用1次和完全背包无限次之间。最直接的做法是枚举每个物品取了多少个转移方程变成dp[i][j] max(dp[i-1][j - k*w[i]] k*v[i])其中0 k c[i]且k*w[i] j。复杂度O(nCC)严格说是O(nC平均c[i])在面试题里基本会超时需要优化。多重背包最常用的优化是二进制拆分。核心思想一个物品的c[i]个可用次数可以拆成若干个01背包物品每个拆分出来的物品重量是w[i] * (2^k)价值是v[i] * (2^k)把所有拆分后的新物品跑一遍01背包即可。为什么是2的幂因为[1,2,4,...,剩余]这个组合能表示0到c[i]之间的任意整数这是二进制表示的基本原理。举个例子如果c[i]10可以拆成1、2、4、310-1-2-43四个新物品这四个数任意组合能覆盖0到10的所有整数。代码实现如下def knapsack_multiple(n, C, w, v, c): new_w, new_v [], [] for i in range(n): # 二进制拆分 k 1 while k c[i]: new_w.append(w[i] * k) new_v.append(v[i] * k) c[i] - k k 1 if c[i] 0: new_w.append(w[i] * c[i]) new_v.append(v[i] * c[i]) # 01背包跑一遍 dp [0] * (C 1) for i in range(len(new_w)): for j in range(C, new_w[i] - 1, -1): dp[j] max(dp[j], dp[j - new_w[i]] new_v[i]) return dp[C]我来解释一下这段代码里几个值得注意的点while k c[i]从1开始不断乘2直到超过剩余次数。每次拆分出一个重量为w[i]*k、价值为v[i]*k的新物品。最后if c[i] 0处理剩余次数比如10拆完1、2、4后还剩3就拆一个3个一起的组。这3个一组要和1、2、4组合起来恰好覆盖到10。拆分完成后新物品的取或不取本质上就是在决定原始物品取k个这个决策所以直接套01背包的模板就行。注意二进制拆分后物品数量从n变成了O(nlog(max(c)))级别所以整体复杂度是O(n * log(c) * C)。这个优化在面试中属于进阶考点如果面试官没主动问可以在写完基础多重背包解法后主动提一句如果用二进制拆分可以优化到O(nlog(c)*C)会加分不少。4.3 三兄弟对比速查表为了方便记忆和快速查阅我把三种背包的核心差异整理成一张表问题类型物品可用次数一维遍历顺序转移方程一维典型复杂度01背包最多1次倒序dp[j] max(dp[j], dp[j-w]v)O(n*C)完全背包无限次正序dp[j] max(dp[j], dp[j-w]v)O(n*C)多重背包最多c[i]次拆分后按01背包先拆分再走01背包O(n*log(c)*C)这张表最底层的规律是遍历顺序不是拍脑袋定的而是由转移方程依赖上一行还是同一行的值决定的。01背包转移依赖dp[j-w]里不含当前物品的最优值所以要保证它不被当前更新污染——倒序完全背包转移依赖dp[j-w]里已包含当前物品的最优值所以要用当前更新的结果——正序。把这个逻辑讲清楚遍历顺序就不会记反。5. 从经典模板到高频变种面试题真正考你的地方5.1 恰好装满初始化方式的微调背包问题最常见的一个变种是要求恰好装满背包而不是不超过容量。比如LeetCode 322题零钱兑换问凑出amount金额需要的最少硬币数LeetCode 416题分割等和子集问能否选出若干数恰好等于总和的一半。这类题和标准背包的差别在初始化上这一点很多人踩坑。回顾标准背包我们初始化所有dp[j] 0含义是容量j下可以不装任何东西价值为0。但恰好装满的语义下容量为0时恰好装满的方案是存在的什么都不选价值为0但容量大于0时如果没有合法方案应该初始化为负无穷求最大值时或正无穷求最小值时表示目前无法恰好凑满。拿LeetCode 322举例子dp[j]表示凑出金额j所需的最少硬币数。初始化dp[0]0其他dp[j]float(inf)。这样在状态转移时dp[j] min(dp[j], dp[j-coin] 1)只有当dp[j-coin]不是无穷大时dp[j]才能被更新为有效值。如果没有这个初始化dp[5]可能被错误地更新成inf1之类的垃圾值。用暴力枚举类比你枚举所有可能凑出金额j的组合如果凑不出来结果应该是不存在而不是凑了0个硬币。初始化就是提前告诉DP表除容量0外其他容量目前都凑不满。注意我见过候选人写恰好装满的题时代码逻辑全对就是初始化的正负无穷设置错了方向。求最小值用float(inf)求最大值用float(-inf)这个别看反了。5.2 求方案数加号变求和另一个高频变种是求方案数。比如LeetCode 494题目标和给你一个数组每个数前面可以加正号或负号问有多少种方法让最终结果等于target。如果你被背包的最大价值思维定式锁住可能半天想不出来。但实际上这类题只是把转移方程里的max换成而已。具体来说定义dp[j]表示凑出数值j的方法数那么状态转移就是dp[j] dp[j - num]。含义是当前数取正的话要凑出j前面得先凑出j-num方案数是dp[j-num]当前数取负的话前面得先凑出jnum方案数是dp[jnum]。这里要注意的是遍历顺序和初始化初始化dp[0]1因为凑出0只有一种方法——什么都不选。做完状态转移后答案就是dp[target]可能需要处理偏移量因为负数下标不支持。这类题目只要识别出计数两个字就不应该继续套max/min模板而是换成累加。5.3 二维费用背包状态多一个维度还有一种变种是二维费用背包背包限重的同时限体积。比如LeetCode 474题一和零给你若干字符串每个字符串里有若干个0和1问在最多能用m个0和n个1的限制下最多能选多少个字符串。这类题的状态要从二维变成三维dp[i][j][k]表示前i个物品在0的容量为j、1的容量为k时的最大选择数。通常可以压缩成二维滚动数组dp[j][k]外层遍历物品内层两个容量维度都要倒序遍历因为压缩后要用旧值。转移方程就是01背包的二维版for s in strs: zeros s.count(0) ones len(s) - zeros for j in range(m, zeros - 1, -1): for k in range(n, ones - 1, -1): dp[j][k] max(dp[j][k], dp[j - zeros][k - ones] 1)面试中遇到二维费用的变种判断标准很简单题目里同时出现两个独立限制条件比如重量体积、0的数量1的数量转移时就需要两个维度同时参与。5.4 背包装物品还是装字数识别变种的换皮套路我来总结一个判断变种题型的方法面试题经常把背包装进各种故事里但底层状态定义万变不离其宗。怎么快速识别看三个点题目问的是最大价值/最小代价还是方案数——max/min还是求和每个物品/元素能不能重复用——决定01背包还是完全背包有没有恰好的约束——决定初始化的正负无穷举个例子LeetCode 139题单词拆分给定一个字符串s和一个单词字典wordDict问s能否拆分成若干个字典里的单词。看起来和背包八竿子打不着但你可以把s[0:i]能否拆分看作状态dp[i]从位置j切一刀如果dp[j]为真且s[j:i]在字典里那dp[i]就为真。这本质上就是一个每个单词可以用无限次的完全背包求可行性问题。识别出这个对应关系代码就很好写了。6. 面试实战拿到DP题的10分钟思考顺序6.1 从记忆化搜索到DP先写暴力递归再优化面试过程中很多人容易犯的毛病是拿到题目直接开始写状态转移方程结果卡在定义上越写越乱。我建议的流程是前2-3分钟先用暴力递归的思维把问题描述清楚。比如01背包暴力递归其实就是def dfs(i, rest_capacity): if i n: return 0 # 不取第i个 res dfs(i 1, rest_capacity) # 取第i个如果放得下 if rest_capacity w[i]: res max(res, dfs(i 1, rest_capacity - w[i]) v[i]) return res然后你观察这个递归函数它有i和rest_capacity两个参数这说明状态有两个维度。再用一个memo缓存计算结果就变成了记忆化搜索。最后把递归改成循环填表就得到了标准的DP解法。这个过程其实是在帮你理清状态定义和转移逻辑比硬想方程要容易得多。面试时我强烈建议你把这个推理路径说给面试官听先写递归再指出重复子问题再加备忘录再转递推。这个过程本身就展示了你的问题拆解能力比直接甩dp[i][j]的公式令人信服得多。6.2 边界条件检查的三个固定步骤写完DP代码之后不要急着说做完了。花10秒钟做三件事检查数组长度dp数组的长度是C1还是C有没有越界风险检查初始化的语义容量0的值是不是符合题目要求不等价于0的情况恰好装满、最小值有没有特殊处理检查遍历方向内层循环是正序还是倒序有没有可能覆盖还没用的旧值这三个步骤能挡住大部分运行时错误。我见过不少人栽在数组初始化长度为C但访问了dp[C]这种低级错误上面试时这种错误比算法不会更扣分因为它说明你平时写代码不够细心。6.3 空间优化的分寸感不要一上来就写一维我在面试中观察到一个很有意思的现象候选人写01背包一上来就写一维滚动数组的版本。代码确实没问题但面试官追问为什么倒序时答不上来。这有点像背题。我的建议是如果面试官没有明确要求优化空间你可以先写二维版本讲清楚状态定义和转移逻辑然后主动说这个版本空间复杂度是O(n*C)我可以优化成O(C)。这样展示了两层能力能写出正确解也懂优化。反过来如果先写一维被追问的时候紧张了容易露怯。当然如果题目本身的数据范围很大比如C到10^6二维数组根本开不下就直接写一维同时解释为什么可以滚动更新。6.4 被追问能再优化吗时的三种思路面试官经常在常规解法之后追问还有其他优化吗这个时候可以从三个角度思考时间优化能否减少状态维度能否用单调队列优化多重背包这个比较深一般不问空间优化滚动数组、原地更新、用short类型存值等剪枝优化物品按性价比排序用上界剪枝这偏向搜索DP题较少用其中空间优化是最高频的追问方向其次是如果物品数量很大但容量很小怎么办这种问题——答案是把思路反过来容量维度小就用容量做状态物品多没关系。7. 给刷题人的三个实测建议文章最后这个部分我想分享几个自己刷题和面试过程中的实际体会不展开成章节了就写最实用的三条。第一条背包问题的代码量其实很少难的是识别和变通。我建议你把这篇文章里的三类背包模板01、完全、多重自己手写三遍每次写都先口述一遍为什么倒序/正序/二进制拆分再动笔。这样练下来的效果比刷十道同类型题都好。第二条刷动态规划题的时候建议专门用一个笔记记录每道题的状态定义转移方程初始化不用写完整代码。面试前翻一翻笔记比重新刷一遍题高效得多。动笔写的过程本身会逼迫你理清思路这是纯看题解学不到的。第三条也是最重要的一条面试时如果卡住了不要慌试着用暴力递归开始讲思路。面试官要看的不是你一次写对而是你在不知道正解时的思考路径。动态规划这个题型尤其如此很多候选人是会做的都会稍微变形就废本质原因就是没有从暴力递归的底层逻辑去理解状态定义。从递归到DP这个推导链是你面试复习中最值得花时间的部分。背包问题这块内容基本就是这些了下一篇系列里我打算聊一聊区间DP和树形DP这两个方向在面试中也经常出现而且思维方式和背包类问题又不一样到时候再把我踩过的坑和总结的技巧一并分享出来。