企业官网建设流程全解析

动态规划（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 best

1.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要按什么顺序遍历？

如果正序遍历，假设背包容量W=5，当前物品重量w=2、价值v=3。计算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个原始物品，你可以选"1+4"这两组；想选11个，可以选"4+6+1"。每一组都只能选一次，但通过组合它们的不同子集，就能构造出任意数量的原始物品。

代码模板如下（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的位置，导致拆出来的组合无法覆盖所有数量。建议写完后用几个小数据验证一下，比如c=13时拆出的组是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; deque<int> 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; vector<int> 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写成外层容量、内层硬币，得到的答案明显偏大，就是因为同一个组合像"2+3"和"3+2"这种顺序不同的情况被各算了一次。

5.3 字典序最小的方案

这是竞赛题里很有区分度的一问。思路分两步：先正向做一遍DP，然后从最后一个物品开始倒推，每次判断"当前物品能否被选中，并且选中后剩余容量还能达到最大价值"。

更标准的方法是：把物品编号从1到n，DP时让更新严格取"不选物品"优先，倒推时从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 零钱兑换

这题是"恰好装满求最少硬币数"的完全背包经典版本。初始化成一个大数INF，dp[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，并输出装到的最大总价值。

解题流程：

1. 先用二进制拆分把每种商品拆成若干01物品。
2. 初始化dp[0]=0，其余为-INF。
3. 跑01背包。
4. 最后判断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可以解决的模型。我会建议他们按三步走：

1. 确定决策变量：每次在做什么选择？
2. 确定状态表示：选择做完后，哪些信息会影响后续决策？这些信息就是状态的维度。
3. 确定转移顺序：当前决策依赖哪些更早的决策，依赖关系决定了循环的嵌套顺序和方向。

这三步对任何DP都适用，不仅限于背包。一旦你习惯了这种"输入到状态到转移"的翻译过程，面对新题型就不会慌。

8. 我调试背包问题多年的十个"一测就挂"清单

最后分享一份我debug背包问题常用的问题清单，都是平时团队里新人反复踩的坑：

1. 物品索引从0开始还是从1开始搞混，导致j-w[i]访问越界。
2. 容量循环的边界写成j >= 0而不是j >= w[i]，浪费效率，还容易在j-w[i]为负时出错。
3. 数组默认初始化为0，但题目要求恰好装满，忘记改初始化。
4. 方案总数问题里，用max而不是sum做转移，或者把dp[0]初始化为0而不是1。
5. 完全背包和01背包顺序搞反，一道题5分钟写完，样例过不了而且查不出来。
6. 二进制拆分时忘了处理剩余部分，导致拆分不完整，小数据能过，大数据直接WA。
7. 多重背包的容量上限错误，直接把W当数组大小，没有考虑W+w[i]之类的扩展。
8. 大价值相加时用 int 溢出，应该用 long long 却没有用。
9. 单调队列优化里面队头淘汰条件判断错误，把窗口大小当成容量而不是数量c。
10. 倒推方案时，判等条件写成了>=，导致字典序不符合要求，或选中了不该选的物品。

针对前三条，我的建议是写模板代码时固定一套风格：物品从1开始编号，容量从0到W，数组开W+2的冗余空间。这样能显著减少调试成本。针对第9条，如果比赛时时间紧张，直接二进制拆分，不要硬写单调队列，稳才是第一位的。

还有一条心法：任何DP题写完代码，不要立刻交，先自己在脑子里构造一个最小样例，把dp数组从头到尾手工推一遍。这个过程能帮你发现大部分边界错误。我在带集训队时反复强调：你花10分钟手动推一个例子，可能为你省下一次罚时20分钟的WA。

背包问题是一道门。推开门之前，你觉得动态规划是玄学；推开门之后，你会发现所有DP都有共通的骨架——定义状态、找到转移、确定边界。希望这篇不是又一个"教你背模板"的教程，而是帮你把背包问题从"会写代码"提升到"能设计状态"的桥梁。后面再遇到变种题，你可以回头看看这篇里讲的三个基础模型，你会有新的收获。