动态规划DP这个名词很多人在入门阶段背了一堆模板01背包倒着遍历、完全背包正着遍历、多重背包二进制拆一下……代码都能默写可只要题目稍微改个条件比如恰好装满求方案数要求字典序最小立马就懵。我之前带过好几届校队这种情况见得太多了。所以这篇文章不打算再给你讲一遍什么是动态规划而是直接围绕背包问题这条主线把从暴力递归到滚动数组优化、从基础模型到竞赛变种的完整推导链条串起来每一步都讲清楚为什么最后再落到几个真实题目和工程里的资源分配场景上。适合已经写过几道DP题但总感觉没吃透的读者也适合准备算法面试或竞赛集训的人。顺便先回应一个热搜关键词KMP算法算不算动态规划很多人被KMP的next数组误导觉得它像DP。严格说KMP的失配跳转本质是模式串自身的局部匹配信息复用它没有按阶段决策、也没有显式的状态转移方程更接近贪心加回溯的思想和背包问题这种典型DP模型不是一回事。把它和背包放在一起讨论的意义在于两者都很重视状态的抽象但DP的核心是在策略空间中取最优KMP的核心是在已知匹配信息中找最长边界。搞清楚这个区别反而能帮你更准确地理解DP的边界在哪。1. 为什么要拿背包问题当DP进阶的磨刀石背包问题在DP里的地位就像排序算法在基础算法里的地位它足够简单模型足够直观但延展性极强。你可以在背包的框架上叠加几乎所有的DP经典技巧滚动数组、二进制拆分、单调队列优化、状态压缩、路径回溯、方案计数、输出字典序最小解——这些技巧单独拿出来都是一篇教程但在背包问题里它们会自然串联起来。1.1 背包模型为什么天然适合讲状态设计我经常和新人说动态规划第一步不是写代码是回答三个问题这个问题在第几步这个阶段有多少种可能的状态每个状态怎么从上一个阶段转移过来背包问题对这三个问题的回答特别干净阶段就是物品的编号i状态就是当前占用的容量j转移就是考虑当前这个物品放还是不放。正因为模型足够简单你才能把所有注意力集中在DP最核心的思维动作上——把决策过程抽象成状态之间的转移而不是一上来就纠结数据结构怎么搞、边界条件怎么处理。1.2 从所有情况都试一遍到把重复计算缓存下来用一个最简单的例子建立直觉有4个物品重量分别是[2, 1, 3, 2]价值分别是[4, 2, 3, 5]背包容量是5。穷举所有放或不放的组合是2的4次方等于16种当物品数量到30时就是10亿种显然跑不动。但你很快会发现很多不同的选择路径最终落到同一个状态上。比如前两个物品选了第一种没选第二种和前两个物品都没选虽然路径不同但它们对后续决策的影响可能是等价的——只要剩余的容量一样后面物品的选择空间就完全一样。这就是重叠子问题。记忆化搜索的做法就是用一个二维数组记录已经算过的结果下次再遇到同样状态直接返回。def dfs(i, rest): if i n: return 0 if memo[i][rest] ! -1: return memo[i][rest] # 不选第i个物品 best dfs(i 1, rest) # 选第i个物品 if rest w[i]: best max(best, dfs(i 1, rest - w[i]) v[i]) memo[i][rest] best return best1.3 从递归到递推彻底消除函数调用开销记忆化搜索能过题但递归压栈的开销在极限数据下可能成为瓶颈而且很多面试官更希望你直接给出迭代写法。把递归改成递推本质是把从前往后问变成从后往前算状态转移顺序完全由依赖关系决定dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]所以只要按物品编号从小到大、容量从小到大计算就行。这段推导过程非常重要我建议你亲手在纸上把前几个状态填一遍而不是直接背滚动数组的写法。只有搞清楚二维DP表格里每个格子是怎么来的才能理解后面所有优化的动机。2. 01背包状态方程与倒序遍历的物理意义2.1 标准方程与代码骨架01背包的定义是每个物品最多选一次。设dp[i][j]表示前i个物品放进容量为j的背包能获得的最大价值那么不选第i个物品dp[i][j] dp[i-1][j]选第i个物品dp[i][j] dp[i-1][j-w[i]] v[i]所以状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])对应代码for (int i 1; i n; i) { for (int j 0; j W; j) { dp[i][j] dp[i - 1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i - 1][j - w[i]] v[i]); } } }2.2 滚动数组优化为什么必须倒序遍历二维数组的空间复杂度是O(nW)当物品数5000、容量200000时dp[5001][200001]的int数组就要4GB直接爆炸。于是我们观察到dp[i]这一整行的值只依赖dp[i-1]这一行跟更早的行没有任何关系所以可以用一维数组不断覆盖更新。问题来了直接用dp[j] max(dp[j], dp[j-w[i]] v[i])容量j要按什么顺序遍历如果正序遍历假设背包容量W5当前物品重量w2、价值v3。计算dp[2]时用了上一个物品阶段的数据没问题但计算dp[4]时dp[2]已经被当前物品更新过了于是dp[4] max(dp[4], dp[2] 3)里这个dp[2]已经包含了当前物品被选过一次的状态相当于同一个物品被选了第二次。这违反了01背包每个物品最多一次的约束。所以必须倒序遍历容量for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }倒序遍历时每次更新dp[j]用到的dp[j-w[i]]是左侧更小的容量而由于我们从右往左更新左侧的值还没被本轮覆盖所以它仍然保留着上一个物品阶段的数据天然保证了每个物品只被选一次。这个逻辑值得多说一句很多教程只让你背01背包倒着来完全背包正着来但你要是不理解行为差异的本质换一道稍有变化的题就容易栽。倒序的本质不是为了倒序而倒序而是要有意识地控制当前物品的状态有没有可能被重复使用。2.3 初始化语义决定问题答案01背包还有一个特别容易被忽略的坑dp数组初始化成全0和初始化为-INF再置dp[0]0解出来的意义完全不同。全部初始化为0表示背包不一定要装满问的是容量不超过W时的最大价值。此时任意容量j都可以由之前的任何物品组合填充只要不超过j就行。而初始化为负无穷只有dp[0]0表示所有状态必须从空背包精确转移而来最终dp[W]就是恰好装满W的最大价值如果dp[W]还是负无穷说明无法恰好装满。这两种问法在实际题目里非常常见比如给你一堆硬币问凑出amount最少用几枚就是典型的恰好装满问题初始化为大数求最小值。后面第5节我会专门展开。3. 完全背包正序遍历到底改变了什么3.1 方程推导允许重复选择后的状态转移完全背包的问题设定是每种物品有无限个可以重复选择。如果用二维状态继续写转移枚举当前物品选k次dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])注意第二个分支变成了dp[i][j-w[i]]而不是dp[i-1][j-w[i]]。区别在哪前者表示当前这一步我选择再放一个第i种物品放完之后仍然可以考虑继续放第i种物品因为还有无限个所以状态停留在同一行i上继续转移。后者表示放完这个物品之后第i个物品就用完了只能回到i-1这一行。3.2 一维优化后为什么正序就对了把完全背包的二维方程转成一维就是著名的for (int i 1; i n; i) { for (int j w[i]; j W; j) { // 注意正序 dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这次正序是合理的因为计算dp[4]时用到的dp[2]可能已经被当前物品更新过这恰好就是我们想要的——还可以继续选这个物品。正序遍历让当前物品的信息像涟漪一样向右传播每加一次容量就多一次被选中的机会从而实现无限次选择的效果。10行代码就是01背包和完全背包的全部区别。但真正理解这层语义需要想明白一个问题为什么正序遍历能模拟无限次选择我个人的理解是当你处理第i个物品时容量j从w[i]递增到W前面的小容量状态在被时更新时可能已经包含了第i个物品于是后面的大容量状态继承了这一信息并继续叠加价值等价于在一个循环里完成多次取用。3.3 一个容易混淆的细节外层物品、内层容量的顺序不能乱有读者会问如果外层循环容量、内层循环物品行不行对于完全背包确实存在一种写法是外层容量、内层物品它在某些题目里也能得到正确答案而且非常巧妙地避开了每个物品重复取的限制。但我不推荐初学者这么写原因有两个第一交换循环层级后你很难再用一个一个处理物品的直觉去理解状态第二代码的可读性和可维护性会变差。DP的优化可以花哨但核心模型必须清晰。先掌握标准写法再去研究各种等价写法顺序不要颠倒。4. 多重背包从暴力拆解到二进制拆分再到单调队列4.1 最朴素的思路把每个物品当成01背包多重背包的设定是第i种物品有c[i]个。最直接的想法就是把这c[i]个物品逐个展开变成c[i]个独立物品然后套用01背包。这个做法的时间复杂度是O(W乘以所有c[i]的和)当总物品数量很大时会超时。4.2 二进制拆分把数量用指数表示出来二进制拆分的核心思想是任何一个正整数c都可以拆成若干个2的幂之和例如13 1 2 4 6最后一项是剩余部分。拆出来的每一组作为一个大物品重量和价值分别乘以组的大小然后当成01背包处理。这样做可以把物品的重复选择次数从c次压缩到log2(c)次。关键点在于这些2的幂的组合能够表示出1到c之间的任意选择数量这一点可以由二进制加法保证。例如想选5个原始物品你可以选14这两组想选11个可以选461。每一组都只能选一次但通过组合它们的不同子集就能构造出任意数量的原始物品。代码模板如下Python示意items [] # (weight, value) for i in range(n): w, v, c w[i], v[i], c[i] k 1 while k c: items.append((w * k, v * k)) c - k k 1 if c 0: items.append((w * c, v * c)) # 然后对 items 跑 01背包很多新手在拆分时容易漏掉最后的c 0判断或写错k 1的位置导致拆出来的组合无法覆盖所有数量。建议写完后用几个小数据验证一下比如c13时拆出的组是1、2、4、6它们的子集和能覆盖1到13所有整数。这个验证过程比背代码更能帮你建立信心。4.3 单调队列优化O(NW) 的终极形态二进制拆分已经能应付多数竞赛题但遇见卡常数的大数据比如物品数1000、容量100000、每件数量10000二进制拆分的总件数大约是 N * log(max(c))仍然可能吃紧。这时候可以上单调队列优化把每件物品从重复取改成按余数分组取最大值。核心思路是完全背包里dp[j] max(dp[j], dp[j-w] v)可以看作按 j mod w 的余数分成若干个等差数列每一类内部用单调队列维护一个滑动窗口的最大值窗口大小就是该物品的可用个数c。这样每件物品的复杂度从O(W × c)降为O(W)整个算法O(NW)。下面是一个用C写的单调队列优化多重背包模板配合注释说明for (int i 1; i n; i) { int w wgt[i], v val[i], c cnt[i]; for (int mod 0; mod w; mod) { int head 0, tail 0; dequeint dq; // 存下标 // j mod k*w按模分组遍历 for (int k 0; mod k * w W; k) { int j mod k * w; int val dp[j] - k * v; // 关键统一补偿 while (head tail val dp[dq.back()] - (dq.back() - mod) / w * v) dq.pop_back(); dq.push_back(j); // 队头下标对应的扩展次数超出c弹出 if ((j - dq.front()) / w c) dq.pop_front(); dp[j] dp[dq.front()] (j - dq.front()) / w * v; } } }这段代码里最核心也最费解的一行是dp[j] dp[dq.front()] ((j - dq.front()) / w) * v。它的意思是最优转移不一定来自上一次正好减少一个物品的状态而可能来自更早的某个状态中间的差值由若干个当前物品补上。单调队列把每个余数类里面k值递增的候选状态维护成单调递减的队列队头就是窗口内的最大值。我个人建议如果只是应付一般笔试和面试二进制拆分完全够用甚至很多时候比单调队列更容易写对。单调队列优化更适合竞赛选手在必须极限压复杂度时使用不建议作为首发方案。5. 三个高频变种恰好装满、方案总数、字典序最小5.1 恰好装满初始化定生死题目变化不是问容量不超过W的最大价值而是问恰好装满W时的最大价值。做法前面提过一句话这里展开讲。const int NEG_INF -1e9; vectorint dp(W 1, NEG_INF); dp[0] 0; for (int i 0; i n; i) { for (int j W; j w[i]; j--) { if (dp[j - w[i]] ! NEG_INF) dp[j] max(dp[j], dp[j - w[i]] v[i]); } } // 若dp[W]仍为NEG_INF则无法恰好装满为什么这里判dp[j-w[i]] ! NEG_INF很重要因为如果直接用dp[j-w[i]] v[i]参与比较负无穷加上一个正数仍然是一个很大的负数虽然不会影响最终最大值但在求方案数等场景里会造成灾难性的假可达状态。所以正确的姿势是在转移前检查源状态是否可达。用生活化类比就是你想知道从A点出发恰好走满10步能到的所有位置那就必须先确保前9步的状态是真实可达的而不是把从未出发当成一种合法起点。5.2 求方案总数加法原理替代最大值如果题目问有多少种不同的放法刚好装满W状态定义不变转移变成dp[0] 1 dp[j] sum(dp[j - w[i]]) // 对所有能转移的物品求和这里同样有初始化和循环顺序的讲究。01背包求方案数时内层倒序遍历完全背包求方案数例如LeetCode 518零钱兑换II时内层正序遍历。特别注意如果要的是组合数而不是排列数外层必须遍历物品内层遍历容量如果外层遍历容量、内层遍历物品得到的是排列数。这两个结果经常差好几倍题目语言稍微模糊一点就真的会写反。我见过很多人把518写成外层容量、内层硬币得到的答案明显偏大就是因为同一个组合像23和32这种顺序不同的情况被各算了一次。5.3 字典序最小的方案这是竞赛题里很有区分度的一问。思路分两步先正向做一遍DP然后从最后一个物品开始倒推每次判断当前物品能否被选中并且选中后剩余容量还能达到最大价值。更标准的方法是把物品编号从1到nDP时让更新严格取不选物品优先倒推时从n开始往前扫如果dp[i][j] dp[i-1][j-w[i]] v[i]而且这个值大于dp[i-1][j]的严格大于就把物品i加入答案并让 j - w[i]。这样得到的方案在字典序上是最大的编号从大到小选如果想让字典序最小需要先翻转物品顺序再做DP再倒推。这一步逻辑相当容易绕晕建议逐行手推一个5个物品的小例子。6. 实战检验两道经典题和一个竞赛场景6.1 LeetCode 416 分割等和子集题目要求把数组分成两个子集使两个子集和相等。等价于问是否存在一个子集使得子集和等于总和的一半。总和为奇数直接返回false否则跑一遍01背包看容量为total/2是否能达到。def canPartition(nums): total sum(nums) if total % 2: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): dp[j] dp[j] or dp[j - num] return dp[target]这道题是可用性判断型的01背包dp存的不是价值而是能否到达。你需要理解的是为什么可以这么替换背包问题的价值不一定都是数值也可以是bool值关键是转移逻辑里或运算对状态可达性的传递。6.2 LeetCode 322 零钱兑换这题是恰好装满求最少硬币数的完全背包经典版本。初始化成一个大数INFdp[0]0转移时取最小值def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这道题特别容易和5.1的负无穷混淆其实精神一致初始化大数让自己从不可达区分出来然后每次取min。区别只在于这里求的是最小值所以初始值用正无穷。6.3 竞赛实战多重背包 恰好装满的组合题假设这样一道题有N种商品每种有库存c[i]、单件重量w[i]、价值v[i]求能否恰好装到容量W并输出装到的最大总价值。解题流程先用二进制拆分把每种商品拆成若干01物品。初始化dp[0]0其余为-INF。跑01背包。最后判断dp[W]是否为-INF不是则输出 dp[W]。这三种经典操作叠加在一起其实就是把前面几个小节的知识点串起来了。这类综合题的解法依赖于你对每一步优化的原理都有把握一个环节初始化错了整个结果都可能错。7. 从算法题到真实场景资源分配问题里的背包思维背包问题不仅仅存在于LeetCode现实里最典型的就是资源分配。7.1 任务调度中的预算分配假设你是一个项目负责人手上有100万元预算要在5个候选子项目里选择投资组合每个子项目有预估成本c[i]和预估收益p[i]要求总成本不超过预算且每个项目只能决策投/不投。这不就是标准的01背包吗dp[j]表示预算j能获得的最大收益物品就是各个子项目重量是成本价值是收益。7.2 广告投放中的预算分配如果广告平台允许你在同一渠道追加投放且每多投一笔广告费收益增量是稳定的那么每个渠道就有多笔可重复投入的性质这就变成了完全背包。再如果每个渠道最多只能追加k次就变成了多重背包。7.3 为什么说建模思维比模板更重要我辅导过不少刚转行的朋友他们普遍的问题不是不会写DP而是不会把一个业务问题翻译成DP可以解决的模型。我会建议他们按三步走确定决策变量每次在做什么选择确定状态表示选择做完后哪些信息会影响后续决策这些信息就是状态的维度。确定转移顺序当前决策依赖哪些更早的决策依赖关系决定了循环的嵌套顺序和方向。这三步对任何DP都适用不仅限于背包。一旦你习惯了这种输入到状态到转移的翻译过程面对新题型就不会慌。8. 我调试背包问题多年的十个一测就挂清单最后分享一份我debug背包问题常用的问题清单都是平时团队里新人反复踩的坑物品索引从0开始还是从1开始搞混导致j-w[i]访问越界。容量循环的边界写成j 0而不是j w[i]浪费效率还容易在j-w[i]为负时出错。数组默认初始化为0但题目要求恰好装满忘记改初始化。方案总数问题里用max而不是sum做转移或者把dp[0]初始化为0而不是1。完全背包和01背包顺序搞反一道题5分钟写完样例过不了而且查不出来。二进制拆分时忘了处理剩余部分导致拆分不完整小数据能过大数据直接WA。多重背包的容量上限错误直接把W当数组大小没有考虑Ww[i]之类的扩展。大价值相加时用 int 溢出应该用 long long 却没有用。单调队列优化里面队头淘汰条件判断错误把窗口大小当成容量而不是数量c。倒推方案时判等条件写成了导致字典序不符合要求或选中了不该选的物品。针对前三条我的建议是写模板代码时固定一套风格物品从1开始编号容量从0到W数组开W2的冗余空间。这样能显著减少调试成本。针对第9条如果比赛时时间紧张直接二进制拆分不要硬写单调队列稳才是第一位的。还有一条心法任何DP题写完代码不要立刻交先自己在脑子里构造一个最小样例把dp数组从头到尾手工推一遍。这个过程能帮你发现大部分边界错误。我在带集训队时反复强调你花10分钟手动推一个例子可能为你省下一次罚时20分钟的WA。背包问题是一道门。推开门之前你觉得动态规划是玄学推开门之后你会发现所有DP都有共通的骨架——定义状态、找到转移、确定边界。希望这篇不是又一个教你背模板的教程而是帮你把背包问题从会写代码提升到能设计状态的桥梁。后面再遇到变种题你可以回头看看这篇里讲的三个基础模型你会有新的收获。