动态规划是面试算法题里最考验基本功的类型之一。这个系列写到第十篇经典动态规划的第二部分该把压箱底的东西掏出来了。如果说前面的题目是在帮你建立“状态怎么想”的感觉那今天这篇就是冲着面试里最常考的经典模型去的——01背包问题。不是单纯让你背代码而是要讲清楚面试官为什么要反复问背包、他怎么从一道裸题给你变出花来、你拿到题之后第一眼该怎么判断这就是背包类动态规划以及最关键的那个坑——空间优化到底为什么容易写反。这篇适合正在刷题准备面试的读者也适合已经刷了不少题、但对背包模型始终觉得“会做这道、不会做那道”的人。看完你会有一种感觉原来背包类动态规划不是一堆题而是一个可以举一反三的框架。1. 为什么背包问题被面试官反复点名先聊个现象。你去翻各大公司的面经题库动态规划相关的题目背包问题出现的频率非常高。而且很有意思的是面试官一般不会直接说“来写个01背包”因为你会背。他一定会给你穿个马甲比如“分割等和子集”“目标和”“零钱兑换”“单词拆分”这些题表面的名字五花八门剥开壳一看内核全是背包。为什么背包问题这么受偏爱我自己的理解是动态规划本身考察的核心能力有两个一是状态定义能力二是决策分析能力。而背包问题恰好把这两件事压缩到了最小尺度让你在十几分钟的面试对话里就能完整展示出来。状态定义dp[i][j] 里 i 和 j 分别代表什么为什么是这个含义而不是别的。决策分析第 i 件物品你到底是“拿”还是“不拿”拿之前要满足什么条件拿了之后状态怎么转移。边界处理dp[0][j] 和 dp[i][0] 应该初始化为多少这直接决定答案对不对。优化意识能不能从二维状态压到一维压完之后遍历顺序为什么要反着来。这四个点正好是面试官评价一个候选人动态规划水平的核心维度。所以他不问你别的就问背包——这一道题就能同时探出你的四项底细。这也是为什么很多候选人的反馈是“背包题我明明刷过但面试官一变形我就懵了”本质上是只记住了代码没理解模型。这里我还要多说一句。有不少人觉得背包题太“老”了现在面试是不是不怎么考了我的观察是恰恰相反背包不仅没被淘汰反而是很多中等难度动态规划题的“底层操作系统”。而且越是大型公司越喜欢用这种经典模型去考察你能不能从底层原理出发去套用到新题目上。新瓶装旧酒酒还是那瓶酒。2. 从“拿还是不拿”开始01背包的状态设计与转移推导先回到最原始的01背包问题。给定 n 个物品每个物品有一个重量 w[i] 和一个价值 v[i]你有一个容量为 C 的背包问能装下的最大价值是多少。这里的“01”指的是每件物品只有两种状态拿1或者不拿0不能拿半件也不能拿多件。很多人一上来的直觉是用贪心——按单位价值排序先装性价比高的。但经典的 counterexample 是一个容量10的背包物品A重量6价值12物品B重量5价值10物品C重量5价值10。按单位价值贪心你应该先拿A剩下4的容量装不了B也装不了C总价值12。但最优解明明是拿B和C总价值20。这就是为什么背包不能贪心必须穷举所有组合。穷举的朴素做法是枚举所有子集2 的 n 次方种可能n 到了 20 就扛不住了。动态规划的思路不是去枚举组合而是去记录“同一个容量下最优的价值是多少”。2.1 状态定义dp[i][j] 的两个维度各有讲究dp[i][j] 表示从前 i 个物品中选总重量不超过 j 的前提下能获得的最大价值。这个状态定义要仔细品因为后边所有变体的根基都在这里。i 是“已经考虑过的物品集合”j 是“当前背包的剩余/已用容量”。很多人一开始会觉得这两个维度有重复其实没有。物品维度解决了“每个物品只能选一次”的约束容量维度解决了“总重量不能超过背包上限”的约束。定义好状态之后接下来最大的问题就是dp[i][j] 怎么从之前的状态推出来这就要分析第 i 个物品的决策了——它只有两种可能。2.2 转移方程理解“不放”和“放”两条路第 i 个物品代码里对应下标 i-1重量 w价值 v。面对它的时候你只有两个选择不放那问题就退化成“从前 i-1 个物品中选总重量不超过 j”也就是 dp[i-1][j]。放那必须保证当前容量 j 至少能装下 w同时你要给这个物品腾出 w 的空间剩下的 j-w 容量去装前 i-1 个物品里的最优组合。总价值就是 dp[i-1][j-w] v。所以转移方程长这样dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v) 当 j w 时 dp[i][j] dp[i-1][j] 当 j w 时这里值得强调两个容易忽略的细节。第一为什么“放”的时候要用 dp[i-1][j-w] 而不是 dp[i][j-w]因为 01 背包要求每个物品只能选一次你既然决定选第 i 个那前 i-1 个物品里就不应该再包含它所以必须从 i-1 层转移。第二j-w 这个下标意味着你是在“预留空间”不是先装满了再往上加这个思考顺序是从“决策”反推“转移”的关键。2.3 完整代码与复杂度分析def knapsack_01(weights, values, capacity): n len(weights) # dp[i][j]: 前 i 个物品容量为 j 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w, v weights[i - 1], values[i - 1] for j in range(1, capacity 1): if j w: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][capacity]时间复杂度 O(n * C)空间复杂度 O(n * C)。很多初学者会问为什么容量维度要从 1 遍历到 capacity而不是从 w 开始因为代码里把 j w 的情况也更新了一遍这样是为了让 dp[i][j] 的每一格都有值后边找答案的时候 dp[n][capacity] 一定是完整的。如果你不想每个容量都赋值也可以让 j 从 w 开始遍历但要记得先把 dp[i][j] 初始化成 dp[i-1][j]。我一直觉得背包问题的二维表格画一遍比看十遍代码都管用。横轴是容量 j纵轴是物品 i每个格子是你填出来的最大价值。你填第 i 行的某个格子时只看上一行i-1对应位置和左边某个位置这样“状态只依赖前一层”的结构会让你对动态规划的无后效性有更直观的理解。2.4 为什么这个模型是“基础款”把01背包的转移方程和后面遇到的很多题目对照你会发现很多题都是这个骨架换了个壳。比如“分割等和子集”给你一个数组问能不能分成两个和相等的子集。翻译一下就是能不能从数组里选一些数让和恰好等于总和的一半。这就是把物品的价值和重量都当成数值本身目标从“最大价值”变成“能否凑出某个和”。所以我在面试刷题时养成一个习惯拿到动态规划题先别急着写代码先把题目里的“物品”是什么、“容量”是什么、“价值”是什么找出来。这三个问题一回答背包模型基本就套上了。3. 面试官最爱的变体从01背包到完全背包、分组背包、求方案数面试的时候直接考裸01背包的概率很低。更多时候面试官会在你写完基础版本之后开始“加戏”。常见的有这么几种变法每一种背后都有它的考察意图。我按出现频率排个序一个一个说。3.1 变体一完全背包物品无限量完全背包和01背包唯一的区别是每种物品你可以拿任意多件。这时候转移方程就变了因为第 i 个物品拿了之后你还可能继续拿它。所以“拿”的转移不再是 dp[i-1][j-w]v而是 dp[i][j-w]v——注意这里第 i 行的意思是“拿了之后还能继续从当前物品里选”。def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) n len(weights) for i in range(n): w, v weights[i], values[i] for j in range(w, capacity 1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]你看代码和01背包优化版唯一的区别就是内层循环从倒序变成了正序。这个正序不是随便写的它恰好利用了“一维数组更新时后面的值会用到本轮刚更新的值”这个特性来实现无限取同一个物品的效果。这里不展开太多后面第4章会专门讲空间优化我把这两个放到一起对比会更清楚。3.2 变体二分组背包每组只能选一个有的面试题会把物品分组比如每组里有若干个商品但你最多只能从一组里选一个。经典场景是你有很多类商品每类里选一个最划算的。这种题的状态定义和多了一个“组”的维度处理方式是在遍历顺序上做文章。三层循环先遍历组再遍历容量最后遍历组内物品。容量遍历要放在组内物品遍历的外面这样保证“每组最多选一个”。如果顺序反了就变成了每组可以选多个直接出bug。3.3 变体三从“最大值”到“方案数”初始化是关键有些题不问你最大价值而是问你“有多少种凑法”。比如找零钱有多少种方案。这种题不是用 max 做转移而是把 max 换成求和dp[j] dp[j] dp[j - coin]这里最大的坑是初始化。dp[0] 必须等于 1表示“凑出0元有1种方案——什么都不选”。如果你初始化成 0那后面全是 0。很多人在这个点上栽过跟头面试时如果结果差了十万八千里先检查 dp[0]。还有个更隐蔽的变体有的题区分组合顺序。比如凑零钱时[1,2] 和 [2,1] 算两种还是算一种如果算两种遍历顺序要放在外层先遍历容量再遍历硬币如果算一种先遍历硬币再遍历容量。这个细节在LeetCode 518和377这两个题上体现得特别明显建议拿出来对比做一遍。3.4 变体四二维费用的背包有些物品有两个维度的限制比如重量和体积都不能超。这时候状态就从 dp[i][j] 变成 dp[i][j][k]多了一维容量限制。做法也很直白再加一层循环。我在面试中遇到这类题的经验是二维费用背包考的本质其实是“你能不能举一反三把一维模型推广到多维”难度本身不大但如果你连01背包的状态定义都没吃透到这一步就会彻底乱掉。下面这个表是我自己复习时整理的把常见背包变体做了一个横向对比。面试前花十分钟扫一眼比盲目刷题效率高得多。变体类型物品数量限制内层循环方向典型问法01背包每件最多1次倒序 j: C → w最大价值完全背包每件无限次正序 j: w → C最大价值 / 凑法数量分组背包每组最多1个先组 → 再容量 → 再组内物品每组选一个的最大价值求方案数视物品而定同01或完全多少种凑法恰好装满视物品而定同01或完全是否恰好能凑出4. 空间优化是个加分项但也是翻车重灾区说句实话面试里你把二维dp写出来能讲清楚转移逻辑基本已经及格了。但如果你想拿高分空间优化是绕不开的加分项。面试官大概率会追问一句“你的空间复杂度能不能再优化一下”这时候如果你能稳地写出滚动数组版本并且解释清楚为什么内层循环要倒序遍历印象分会立刻不一样。4.1 降维从二维到一维的推导逻辑回到01背包的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)你会发现第 i 行只依赖第 i-1 行跟更早的行没关系。那我能不能只保留一行每次更新都用“上一行的旧值”覆盖掉这就是滚动数组的核心思路。改写成一维之后dp[j] 的含义就变成了“当前物品处理到某个阶段时容量 j 能装的最大价值”。因为一行里只能存一份数据你更新 dp[j] 时必须保证用到的 dp[j] 和 dp[j-w] 还是“上一轮”的旧值千万不能用已经被本轮更新过的新值。4.2 为什么01背包内层循环必须倒序这是面试里最高频的追问之一。你想想如果正序遍历假设容量 C10当前物品 w5v10。当 j5 时dp[5] 更新为 max(dp[5], dp[0]10)10。当 j10 时dp[10] 更新为 max(dp[10], dp[5]10)20。问题就出在这——dp[5] 已经被本轮更新过了它已经代表了“拿了当前物品”的状态你再用它去更新 dp[10]就相当于把同一件物品拿了两次违反了01背包“每件最多一次”的约束。反过来如果倒序遍历j10 时dp[10] 用 dp[5] 更新此时 dp[5] 还是上一轮的旧值没被污染。j5 时dp[5] 再用 dp[0] 更新这时候无论怎么更新都不会出现同一件物品被拿两次的情况。所以01背包的一维优化版内层容量循环必须从大到小完全背包的一维版则恰恰相反需要从小到大。能把这个因果链条用大白话讲清楚面试官就知道你是真懂了不是死记硬背。我见过一个候选人把这段讲完之后面试官直接把下一道题从medium跳到了hard——因为他已经证明了基础模型的理解深度。4.3 一维写法与二维写法的一个隐蔽差异很多人把二维转一维时容易漏一个细节。二维版本里你可以写“if j w: dp[i][j] dp[i-1][j]”来显式处理容量不够的情况但一维版本里如果你写for j in range(capacity, -1, -1)当 j w 时 j-w 会是负数容易出现越界或者错误结果。所以一维版本的内层循环下界要写成 w也就是说for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v)这行代码等价于小于 w 的所有容量不可能放进当前物品所以它们保持原样就行不需要任何更新。空间优化的另一个常见翻车点是初始值的设置。如果你求的是“恰好装满”dp[0] 要初始化为0其他 dp[j] 初始化为负无穷因为“恰好装满”这件事在很多容量下是做不到的必须用负无穷表示不可达。如果你求的是“不超过容量”那全部初始化为0就行。这两个的区别我在面试中解释过无数次每次都能看到对方眼神从困惑到恍然大悟——初始化值的选取本质上是你在定义“状态是否可达”的边界。5. 面试现场如何一眼看穿“这题是背包”这一章聊聊我在面试和刷题中总结的实战方法论——拿到一道动态规划题怎么最快判断它是不是背包类问题以及后续怎么处理。5.1 三问定位法第一反应先问三个问题题目里有没有一个“容量”概念比如 sum/2、amount、target这些都可以是容量。题目里有没有一堆“物品”数组的每个元素或者每种面值的硬币这些就是物品。题目里有没有“价值”目标最大价值、最小个数、能不能凑出、有几种凑法。三个问题全中这题基本就是背包了。拿 LeetCode 416“分割等和子集”举例数组元素就是要选的物品总和的一半就是容量问“能不能恰好凑出”就是价值目标。再拿 LeetCode 322“零钱兑换”举例硬币面值就是物品每种无限个所以是完全背包amount 是容量问“最少用几个硬币”这就是最小化目标下的完全背包。5.2 套模型的完整代码示例下面用最典型的“分割等和子集”来演示一遍完整流程。def can_partition(nums): total sum(nums) # 总和是奇数铁定不可能分成两个相等子集 if total % 2 1: return False target total // 2 dp [False] * (target 1) dp[0] True # 容量为0时什么都不选就恰好凑出 for num in nums: for j in range(target, num - 1, -1): dp[j] dp[j] or dp[j - num] return dp[target]这里有三个关键点容易出错。第一target 是总和的一半如果总和是奇数直接返回 False这一步别看简单能帮你省下一大堆无效计算。第二dp 数组用布尔值而不是整数因为题目问的是“能不能”不是“最多能装多少”。第三内层循环为什么倒序因为这是01背包——每个数只能用一次。面试时写完这题面试官通常会追问“如果数组里有负数或者有0怎么办”。这是一个很典型的扩展问题。如果数组里有0你会发现 dp[j] dp[j] or dp[j-0] 会导致 j 永远原地打转不过实际上因为 for 循环 j 一直在减少而 num0 的情况 j - 0 j所以 dp[j] dp[j] or dp[j]不会产生任何变化也就是说0元素不影响布尔值的正确性但它会让“方案数”版本的题目出现无穷多方案那就需要特殊处理。负数的情况则更难因为“总和的一半”这个前提会变需要把数组平移偏移量。5.3 代码模板从裸题到变形题都能套我把刷了这么多背包题之后沉淀下来的“模板骨架”分享出来你背住这个骨架再针对变体做小修改即可。# 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) # 完全背包基础骨架物品无限量容量正序遍历 for item in items: for j in range(item.weight, capacity 1): dp[j] max(dp[j], dp[j - item.weight] item.value) # 求方案数把 max 换成求和 dp[0] 1 # 关键初始化 for item in items: for j in range(capacity, item.weight - 1, -1): dp[j] dp[j - item.weight] # 恰好装满dp[0]0其他初始化为负无穷/正无穷 dp [float(-inf)] * (capacity 1) dp[0] 0这个骨架吃透之后遇到背包变形题你只需要回答三件事物品能不能重复选决定内层方向、求的是最大值还是方案数决定转移操作符、容量要不要恰好装满决定初始化。这三个决定一做代码基本就出来了。5.4 反例哪些题长得像背包但实际不是有句话说得好动态规划最大的难点不是写转移方程而是判断该不该写转移方程。我遇到过不少候选人也包括早期的我自己看到题目里有“组合”“划分”就条件反射往背包上套结果翻车。典型反例是 LeetCode 518“零钱兑换II”和 LeetCode 377“组合总和IV”。这两个题问法几乎一样——都是凑方案的个数但518是组合数硬币顺序无关377是排列数顺序有关。如果用同一个模板去套第二个题必错。这里的区别就在于遍历顺序518 要先遍历硬币再遍历容量377 要先遍历容量再遍历硬币。这个我在前面3.3里提到过这里再强调一次就是因为它太容易踩坑了。还有一类题比如“最长递增子序列”“编辑距离”它们也用到动态规划但既没有“容量”约束也没有“物品集合”的概念它们是序列 DP 的范畴强行套背包模型只会让自己越绕越晕。判断的关键还是回到三问定位法——如果找不到明确的“容量”那就放弃背包思路重新从序列状态的角度去定义。6. 背包之外的思考动态规划题型的底层通用套路聊到这儿你可能已经发现了背包问题虽然变化多但它的每一步推导都指向了动态规划的几个通用方法论。我把这些方法论单独拎出来它们不光是背包对其他动态规划题同样适用。状态定义优先于转移方程。很多人一上来就急着写转移方程但转移方程是从状态定义“长”出来的。状态定义里两个维度选什么直接决定了转移方程的复杂程度。初始化值不是拍脑袋定的。dp[0]、dp[0][j]、dp[i][0] 这些边界值本质是你在回答“最基础、什么都不选/容量为0时答案是什么”。遍历顺序决定了状态的依赖方向。正序还是倒序、外层物品还是外层容量这些不是习惯问题而是你有没有真正理解“状态从哪来、能不能重复用”。转移表达式对应问题的语义。max 对应最优解加和对应方案数and/or 对应可达性min 对应最小代价。我在实际刷题过程中发现一个很有用的习惯每做完一道动态规划题不管难易都在题目标注旁边写清楚三件事——状态定义是什么、初始化是什么、遍历顺序是正还是倒。过一段时间回看你就自然形成了一张动态规划题型地图。这个过程比盲目刷一百道题有用得多。面试之前我还会专门花半小时在纸上把01背包、完全背包、求方案数这三个模板默写一遍。不是为了背代码是为了让“为什么倒序”这件事在脑子里再过一遍。面试中一旦遇到背包变体你就不会慌因为你知道无论它怎么穿马甲内核就那几句话。动态规划的题目永远刷不完但经典模型的骨架是可以反复利用的。01背包作为最基础的一座山爬上去之后你看后面那些“爬坡题”的视野视角都会不一样。希望这篇笔记能帮你把这块拼图真正补上而不是又收藏了一份吃灰的代码模板。 
长河君 · 2026/8/29 6:04:33 · 阅读 1.2k 01背包动态规划全解析：从状态定义到空间优化，面试变形题一网打尽
动态规划是面试算法题里最考验基本功的类型之一。这个系列写到第十篇经典动态规划的第二部分该把压箱底的东西掏出来了。如果说前面的题目是在帮你建立“状态怎么想”的感觉那今天这篇就是冲着面试里最常考的经典模型去的——01背包问题。不是单纯让你背代码而是要讲清楚面试官为什么要反复问背包、他怎么从一道裸题给你变出花来、你拿到题之后第一眼该怎么判断这就是背包类动态规划以及最关键的那个坑——空间优化到底为什么容易写反。这篇适合正在刷题准备面试的读者也适合已经刷了不少题、但对背包模型始终觉得“会做这道、不会做那道”的人。看完你会有一种感觉原来背包类动态规划不是一堆题而是一个可以举一反三的框架。1. 为什么背包问题被面试官反复点名先聊个现象。你去翻各大公司的面经题库动态规划相关的题目背包问题出现的频率非常高。而且很有意思的是面试官一般不会直接说“来写个01背包”因为你会背。他一定会给你穿个马甲比如“分割等和子集”“目标和”“零钱兑换”“单词拆分”这些题表面的名字五花八门剥开壳一看内核全是背包。为什么背包问题这么受偏爱我自己的理解是动态规划本身考察的核心能力有两个一是状态定义能力二是决策分析能力。而背包问题恰好把这两件事压缩到了最小尺度让你在十几分钟的面试对话里就能完整展示出来。状态定义dp[i][j] 里 i 和 j 分别代表什么为什么是这个含义而不是别的。决策分析第 i 件物品你到底是“拿”还是“不拿”拿之前要满足什么条件拿了之后状态怎么转移。边界处理dp[0][j] 和 dp[i][0] 应该初始化为多少这直接决定答案对不对。优化意识能不能从二维状态压到一维压完之后遍历顺序为什么要反着来。这四个点正好是面试官评价一个候选人动态规划水平的核心维度。所以他不问你别的就问背包——这一道题就能同时探出你的四项底细。这也是为什么很多候选人的反馈是“背包题我明明刷过但面试官一变形我就懵了”本质上是只记住了代码没理解模型。这里我还要多说一句。有不少人觉得背包题太“老”了现在面试是不是不怎么考了我的观察是恰恰相反背包不仅没被淘汰反而是很多中等难度动态规划题的“底层操作系统”。而且越是大型公司越喜欢用这种经典模型去考察你能不能从底层原理出发去套用到新题目上。新瓶装旧酒酒还是那瓶酒。2. 从“拿还是不拿”开始01背包的状态设计与转移推导先回到最原始的01背包问题。给定 n 个物品每个物品有一个重量 w[i] 和一个价值 v[i]你有一个容量为 C 的背包问能装下的最大价值是多少。这里的“01”指的是每件物品只有两种状态拿1或者不拿0不能拿半件也不能拿多件。很多人一上来的直觉是用贪心——按单位价值排序先装性价比高的。但经典的 counterexample 是一个容量10的背包物品A重量6价值12物品B重量5价值10物品C重量5价值10。按单位价值贪心你应该先拿A剩下4的容量装不了B也装不了C总价值12。但最优解明明是拿B和C总价值20。这就是为什么背包不能贪心必须穷举所有组合。穷举的朴素做法是枚举所有子集2 的 n 次方种可能n 到了 20 就扛不住了。动态规划的思路不是去枚举组合而是去记录“同一个容量下最优的价值是多少”。2.1 状态定义dp[i][j] 的两个维度各有讲究dp[i][j] 表示从前 i 个物品中选总重量不超过 j 的前提下能获得的最大价值。这个状态定义要仔细品因为后边所有变体的根基都在这里。i 是“已经考虑过的物品集合”j 是“当前背包的剩余/已用容量”。很多人一开始会觉得这两个维度有重复其实没有。物品维度解决了“每个物品只能选一次”的约束容量维度解决了“总重量不能超过背包上限”的约束。定义好状态之后接下来最大的问题就是dp[i][j] 怎么从之前的状态推出来这就要分析第 i 个物品的决策了——它只有两种可能。2.2 转移方程理解“不放”和“放”两条路第 i 个物品代码里对应下标 i-1重量 w价值 v。面对它的时候你只有两个选择不放那问题就退化成“从前 i-1 个物品中选总重量不超过 j”也就是 dp[i-1][j]。放那必须保证当前容量 j 至少能装下 w同时你要给这个物品腾出 w 的空间剩下的 j-w 容量去装前 i-1 个物品里的最优组合。总价值就是 dp[i-1][j-w] v。所以转移方程长这样dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v) 当 j w 时 dp[i][j] dp[i-1][j] 当 j w 时这里值得强调两个容易忽略的细节。第一为什么“放”的时候要用 dp[i-1][j-w] 而不是 dp[i][j-w]因为 01 背包要求每个物品只能选一次你既然决定选第 i 个那前 i-1 个物品里就不应该再包含它所以必须从 i-1 层转移。第二j-w 这个下标意味着你是在“预留空间”不是先装满了再往上加这个思考顺序是从“决策”反推“转移”的关键。2.3 完整代码与复杂度分析def knapsack_01(weights, values, capacity): n len(weights) # dp[i][j]: 前 i 个物品容量为 j 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w, v weights[i - 1], values[i - 1] for j in range(1, capacity 1): if j w: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][capacity]时间复杂度 O(n * C)空间复杂度 O(n * C)。很多初学者会问为什么容量维度要从 1 遍历到 capacity而不是从 w 开始因为代码里把 j w 的情况也更新了一遍这样是为了让 dp[i][j] 的每一格都有值后边找答案的时候 dp[n][capacity] 一定是完整的。如果你不想每个容量都赋值也可以让 j 从 w 开始遍历但要记得先把 dp[i][j] 初始化成 dp[i-1][j]。我一直觉得背包问题的二维表格画一遍比看十遍代码都管用。横轴是容量 j纵轴是物品 i每个格子是你填出来的最大价值。你填第 i 行的某个格子时只看上一行i-1对应位置和左边某个位置这样“状态只依赖前一层”的结构会让你对动态规划的无后效性有更直观的理解。2.4 为什么这个模型是“基础款”把01背包的转移方程和后面遇到的很多题目对照你会发现很多题都是这个骨架换了个壳。比如“分割等和子集”给你一个数组问能不能分成两个和相等的子集。翻译一下就是能不能从数组里选一些数让和恰好等于总和的一半。这就是把物品的价值和重量都当成数值本身目标从“最大价值”变成“能否凑出某个和”。所以我在面试刷题时养成一个习惯拿到动态规划题先别急着写代码先把题目里的“物品”是什么、“容量”是什么、“价值”是什么找出来。这三个问题一回答背包模型基本就套上了。3. 面试官最爱的变体从01背包到完全背包、分组背包、求方案数面试的时候直接考裸01背包的概率很低。更多时候面试官会在你写完基础版本之后开始“加戏”。常见的有这么几种变法每一种背后都有它的考察意图。我按出现频率排个序一个一个说。3.1 变体一完全背包物品无限量完全背包和01背包唯一的区别是每种物品你可以拿任意多件。这时候转移方程就变了因为第 i 个物品拿了之后你还可能继续拿它。所以“拿”的转移不再是 dp[i-1][j-w]v而是 dp[i][j-w]v——注意这里第 i 行的意思是“拿了之后还能继续从当前物品里选”。def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) n len(weights) for i in range(n): w, v weights[i], values[i] for j in range(w, capacity 1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]你看代码和01背包优化版唯一的区别就是内层循环从倒序变成了正序。这个正序不是随便写的它恰好利用了“一维数组更新时后面的值会用到本轮刚更新的值”这个特性来实现无限取同一个物品的效果。这里不展开太多后面第4章会专门讲空间优化我把这两个放到一起对比会更清楚。3.2 变体二分组背包每组只能选一个有的面试题会把物品分组比如每组里有若干个商品但你最多只能从一组里选一个。经典场景是你有很多类商品每类里选一个最划算的。这种题的状态定义和多了一个“组”的维度处理方式是在遍历顺序上做文章。三层循环先遍历组再遍历容量最后遍历组内物品。容量遍历要放在组内物品遍历的外面这样保证“每组最多选一个”。如果顺序反了就变成了每组可以选多个直接出bug。3.3 变体三从“最大值”到“方案数”初始化是关键有些题不问你最大价值而是问你“有多少种凑法”。比如找零钱有多少种方案。这种题不是用 max 做转移而是把 max 换成求和dp[j] dp[j] dp[j - coin]这里最大的坑是初始化。dp[0] 必须等于 1表示“凑出0元有1种方案——什么都不选”。如果你初始化成 0那后面全是 0。很多人在这个点上栽过跟头面试时如果结果差了十万八千里先检查 dp[0]。还有个更隐蔽的变体有的题区分组合顺序。比如凑零钱时[1,2] 和 [2,1] 算两种还是算一种如果算两种遍历顺序要放在外层先遍历容量再遍历硬币如果算一种先遍历硬币再遍历容量。这个细节在LeetCode 518和377这两个题上体现得特别明显建议拿出来对比做一遍。3.4 变体四二维费用的背包有些物品有两个维度的限制比如重量和体积都不能超。这时候状态就从 dp[i][j] 变成 dp[i][j][k]多了一维容量限制。做法也很直白再加一层循环。我在面试中遇到这类题的经验是二维费用背包考的本质其实是“你能不能举一反三把一维模型推广到多维”难度本身不大但如果你连01背包的状态定义都没吃透到这一步就会彻底乱掉。下面这个表是我自己复习时整理的把常见背包变体做了一个横向对比。面试前花十分钟扫一眼比盲目刷题效率高得多。变体类型物品数量限制内层循环方向典型问法01背包每件最多1次倒序 j: C → w最大价值完全背包每件无限次正序 j: w → C最大价值 / 凑法数量分组背包每组最多1个先组 → 再容量 → 再组内物品每组选一个的最大价值求方案数视物品而定同01或完全多少种凑法恰好装满视物品而定同01或完全是否恰好能凑出4. 空间优化是个加分项但也是翻车重灾区说句实话面试里你把二维dp写出来能讲清楚转移逻辑基本已经及格了。但如果你想拿高分空间优化是绕不开的加分项。面试官大概率会追问一句“你的空间复杂度能不能再优化一下”这时候如果你能稳地写出滚动数组版本并且解释清楚为什么内层循环要倒序遍历印象分会立刻不一样。4.1 降维从二维到一维的推导逻辑回到01背包的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)你会发现第 i 行只依赖第 i-1 行跟更早的行没关系。那我能不能只保留一行每次更新都用“上一行的旧值”覆盖掉这就是滚动数组的核心思路。改写成一维之后dp[j] 的含义就变成了“当前物品处理到某个阶段时容量 j 能装的最大价值”。因为一行里只能存一份数据你更新 dp[j] 时必须保证用到的 dp[j] 和 dp[j-w] 还是“上一轮”的旧值千万不能用已经被本轮更新过的新值。4.2 为什么01背包内层循环必须倒序这是面试里最高频的追问之一。你想想如果正序遍历假设容量 C10当前物品 w5v10。当 j5 时dp[5] 更新为 max(dp[5], dp[0]10)10。当 j10 时dp[10] 更新为 max(dp[10], dp[5]10)20。问题就出在这——dp[5] 已经被本轮更新过了它已经代表了“拿了当前物品”的状态你再用它去更新 dp[10]就相当于把同一件物品拿了两次违反了01背包“每件最多一次”的约束。反过来如果倒序遍历j10 时dp[10] 用 dp[5] 更新此时 dp[5] 还是上一轮的旧值没被污染。j5 时dp[5] 再用 dp[0] 更新这时候无论怎么更新都不会出现同一件物品被拿两次的情况。所以01背包的一维优化版内层容量循环必须从大到小完全背包的一维版则恰恰相反需要从小到大。能把这个因果链条用大白话讲清楚面试官就知道你是真懂了不是死记硬背。我见过一个候选人把这段讲完之后面试官直接把下一道题从medium跳到了hard——因为他已经证明了基础模型的理解深度。4.3 一维写法与二维写法的一个隐蔽差异很多人把二维转一维时容易漏一个细节。二维版本里你可以写“if j w: dp[i][j] dp[i-1][j]”来显式处理容量不够的情况但一维版本里如果你写for j in range(capacity, -1, -1)当 j w 时 j-w 会是负数容易出现越界或者错误结果。所以一维版本的内层循环下界要写成 w也就是说for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v)这行代码等价于小于 w 的所有容量不可能放进当前物品所以它们保持原样就行不需要任何更新。空间优化的另一个常见翻车点是初始值的设置。如果你求的是“恰好装满”dp[0] 要初始化为0其他 dp[j] 初始化为负无穷因为“恰好装满”这件事在很多容量下是做不到的必须用负无穷表示不可达。如果你求的是“不超过容量”那全部初始化为0就行。这两个的区别我在面试中解释过无数次每次都能看到对方眼神从困惑到恍然大悟——初始化值的选取本质上是你在定义“状态是否可达”的边界。5. 面试现场如何一眼看穿“这题是背包”这一章聊聊我在面试和刷题中总结的实战方法论——拿到一道动态规划题怎么最快判断它是不是背包类问题以及后续怎么处理。5.1 三问定位法第一反应先问三个问题题目里有没有一个“容量”概念比如 sum/2、amount、target这些都可以是容量。题目里有没有一堆“物品”数组的每个元素或者每种面值的硬币这些就是物品。题目里有没有“价值”目标最大价值、最小个数、能不能凑出、有几种凑法。三个问题全中这题基本就是背包了。拿 LeetCode 416“分割等和子集”举例数组元素就是要选的物品总和的一半就是容量问“能不能恰好凑出”就是价值目标。再拿 LeetCode 322“零钱兑换”举例硬币面值就是物品每种无限个所以是完全背包amount 是容量问“最少用几个硬币”这就是最小化目标下的完全背包。5.2 套模型的完整代码示例下面用最典型的“分割等和子集”来演示一遍完整流程。def can_partition(nums): total sum(nums) # 总和是奇数铁定不可能分成两个相等子集 if total % 2 1: return False target total // 2 dp [False] * (target 1) dp[0] True # 容量为0时什么都不选就恰好凑出 for num in nums: for j in range(target, num - 1, -1): dp[j] dp[j] or dp[j - num] return dp[target]这里有三个关键点容易出错。第一target 是总和的一半如果总和是奇数直接返回 False这一步别看简单能帮你省下一大堆无效计算。第二dp 数组用布尔值而不是整数因为题目问的是“能不能”不是“最多能装多少”。第三内层循环为什么倒序因为这是01背包——每个数只能用一次。面试时写完这题面试官通常会追问“如果数组里有负数或者有0怎么办”。这是一个很典型的扩展问题。如果数组里有0你会发现 dp[j] dp[j] or dp[j-0] 会导致 j 永远原地打转不过实际上因为 for 循环 j 一直在减少而 num0 的情况 j - 0 j所以 dp[j] dp[j] or dp[j]不会产生任何变化也就是说0元素不影响布尔值的正确性但它会让“方案数”版本的题目出现无穷多方案那就需要特殊处理。负数的情况则更难因为“总和的一半”这个前提会变需要把数组平移偏移量。5.3 代码模板从裸题到变形题都能套我把刷了这么多背包题之后沉淀下来的“模板骨架”分享出来你背住这个骨架再针对变体做小修改即可。# 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) # 完全背包基础骨架物品无限量容量正序遍历 for item in items: for j in range(item.weight, capacity 1): dp[j] max(dp[j], dp[j - item.weight] item.value) # 求方案数把 max 换成求和 dp[0] 1 # 关键初始化 for item in items: for j in range(capacity, item.weight - 1, -1): dp[j] dp[j - item.weight] # 恰好装满dp[0]0其他初始化为负无穷/正无穷 dp [float(-inf)] * (capacity 1) dp[0] 0这个骨架吃透之后遇到背包变形题你只需要回答三件事物品能不能重复选决定内层方向、求的是最大值还是方案数决定转移操作符、容量要不要恰好装满决定初始化。这三个决定一做代码基本就出来了。5.4 反例哪些题长得像背包但实际不是有句话说得好动态规划最大的难点不是写转移方程而是判断该不该写转移方程。我遇到过不少候选人也包括早期的我自己看到题目里有“组合”“划分”就条件反射往背包上套结果翻车。典型反例是 LeetCode 518“零钱兑换II”和 LeetCode 377“组合总和IV”。这两个题问法几乎一样——都是凑方案的个数但518是组合数硬币顺序无关377是排列数顺序有关。如果用同一个模板去套第二个题必错。这里的区别就在于遍历顺序518 要先遍历硬币再遍历容量377 要先遍历容量再遍历硬币。这个我在前面3.3里提到过这里再强调一次就是因为它太容易踩坑了。还有一类题比如“最长递增子序列”“编辑距离”它们也用到动态规划但既没有“容量”约束也没有“物品集合”的概念它们是序列 DP 的范畴强行套背包模型只会让自己越绕越晕。判断的关键还是回到三问定位法——如果找不到明确的“容量”那就放弃背包思路重新从序列状态的角度去定义。6. 背包之外的思考动态规划题型的底层通用套路聊到这儿你可能已经发现了背包问题虽然变化多但它的每一步推导都指向了动态规划的几个通用方法论。我把这些方法论单独拎出来它们不光是背包对其他动态规划题同样适用。状态定义优先于转移方程。很多人一上来就急着写转移方程但转移方程是从状态定义“长”出来的。状态定义里两个维度选什么直接决定了转移方程的复杂程度。初始化值不是拍脑袋定的。dp[0]、dp[0][j]、dp[i][0] 这些边界值本质是你在回答“最基础、什么都不选/容量为0时答案是什么”。遍历顺序决定了状态的依赖方向。正序还是倒序、外层物品还是外层容量这些不是习惯问题而是你有没有真正理解“状态从哪来、能不能重复用”。转移表达式对应问题的语义。max 对应最优解加和对应方案数and/or 对应可达性min 对应最小代价。我在实际刷题过程中发现一个很有用的习惯每做完一道动态规划题不管难易都在题目标注旁边写清楚三件事——状态定义是什么、初始化是什么、遍历顺序是正还是倒。过一段时间回看你就自然形成了一张动态规划题型地图。这个过程比盲目刷一百道题有用得多。面试之前我还会专门花半小时在纸上把01背包、完全背包、求方案数这三个模板默写一遍。不是为了背代码是为了让“为什么倒序”这件事在脑子里再过一遍。面试中一旦遇到背包变体你就不会慌因为你知道无论它怎么穿马甲内核就那几句话。动态规划的题目永远刷不完但经典模型的骨架是可以反复利用的。01背包作为最基础的一座山爬上去之后你看后面那些“爬坡题”的视野视角都会不一样。希望这篇笔记能帮你把这块拼图真正补上而不是又收藏了一份吃灰的代码模板。