动态规划01背包：一维DP倒序与循环顺序详解

动态规划里有一类题，代码短得离谱，理解起来却能卡住一大片人，01背包就是典型。二维数组版本大部分人都能顺下来，无非是两层循环套一个 max。可一旦把二维压缩成一维，问题就来了：同样一个方程，为什么容量那一层必须从大到小倒着走，为什么循环嵌套只能是物品放外面、容量放里面，一换顺序结果就全错？我当初学这块的时候，把别人的代码抄了三遍还是记不住，因为压根没搞懂背后的依赖关系。后来逼着自己拿纸笔推了一遍状态转移，才发现整个谜题的钥匙就藏在 dp[j - w[i]] 这个下标里。这篇文章不打算给你一句口诀就走人，而是把这个下标背后的依赖链条完整拆开，让你看完之后能自己把循环顺序推出来，而不是靠背。内容适合刚接触背包、或者一维写法总是莫名其妙写错的朋友，全程用大白话加具体数字推演，跟着走一遍基本就能记住。

1. 一维dp到底省了什么：先把二维解法摆出来

1.1 01背包问题的本质：每件物品只有拿或不拿两种选择

01背包的设定非常朴素：有一个容量为 W 的背包，面前摆着 n 件物品，第 i 件重量是 w[i]，价值是 v[i]。每件物品只有两种归宿，要么装进包里，要么留在外面，不存在"装一半"或者"一件塞两遍"的情况。目标是在不超过背包容量的前提下，让装进去的价值总和最大。

和它对应的还有几个变体：完全背包里每件物品可以拿无限次，多重背包里每件物品有固定数量。这几个看着像亲兄弟，但状态转移的细节差别很大，最容易搞混的就是01背包和完全背包。而它俩在一维写法上的唯一区别，恰恰就是容量那一层到底是倒序还是正序。这个点后面会重点掰开揉碎讲，因为这是所有人踩坑最集中的地方。

为什么这个模型值得花这么多篇幅去抠？因为它是最典型的"每个状态只由前面有限个状态推出来"的问题，是理解动态规划里"无后效性"和"状态压缩"这两个抽象概念的最佳素材。一旦把01背包的依赖关系理清楚，再去看其他一维DP，思路会顺畅很多。现实生活中的打包快递、选课凑学分、投资组合分配预算，底层其实都是同一套逻辑。

1.2 二维dp的状态定义与转移方程

先老老实实把二维版本写出来，因为一维版本是它"减肥"之后的结果，根还在二维这里。

定义 dp[i][j] 表示：只考虑前 i 件物品，背包容量为 j 时能装下的最大价值。下标从 1 开始，dp[0][j] 表示一件物品都不考虑，价值自然是 0；dp[i][0] 表示容量为 0，什么都装不下，价值也是 0。

对于第 i 件物品，只有两种决策：

• 不拿它：价值就是 dp[i-1][j]，容量没变，只是可选的物品少了一件。
• 拿它：前提是 j >= w[i]，拿完之后要腾出 w[i] 的空间，价值变成 dp[i-1][j - w[i]] + v[i]。

两者取较大值，转移方程就是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])，当 j >= w[i] dp[i][j] = dp[i-1][j]，当 j < w[i]

注意方程右边两个项都带着 i-1，这是整个问题的核心所在。它表示"这一步的决策只依赖上一层（少一件物品）的状态"。也就是说，在决定第 i 件物品拿不拿的时候，参考的是前 i-1 件物品的最优结果。这个 i-1 在后面会被反复引用，因为一维数组倒序遍历的唯一使命，就是保证右边的 dp[j - w[i]] 仍然停留在 i-1 那一层。

for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { if (j >= w[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]); else dp[i][j] = dp[i-1][j]; } }

这段代码不会出错，但空间是 O(n * W)。当 W 到几万、n 到几千的时候，二维数组可能直接爆内存。于是就动了压缩的念头。

1.3 滚动数组：物品这一维为什么能省掉

观察转移方程，dp[i][j] 只跟 dp[i-1][...] 有关，跟 dp[i-2]、dp[i-3] 一点关系都没有。也就是说，算第 i 层的时候，第 i-1 层是唯一有用的数据，再往前的层全是"历史遗留"，可以直接扔掉。

这就跟刷墙一样：你只需要知道"上一遍漆"的颜色，没必要把前面十遍的漆都留着。于是用一个一维数组 dp[j] 来滚动，每次处理完一件物品，就让这个数组代表"当前已考虑物品集合"下的最优解。处理第 i 件物品之前，dp[j] 里装的是 i-1 层的结果；处理完之后，它就变成了 i 层的结果。

关键点来了：既然要"原地覆盖"，就必须保证覆盖时机不出错。如果更新 dp[j] 的时候，用到的 dp[j - w[i]] 已经被这一轮（也就是第 i 件物品）覆盖过了，那就等于在用一个"已经考虑过第 i 件物品"的状态去推另一个状态，物品 i 就被用了不止一次。这正是正序遍历的致命伤，也是倒序遍历存在的全部理由。换句话说，一维写法不是简单地删掉一个下标，而是配套了一整套遍历规则来维护语义。

2. 一维转移方程与模板代码

2.1 把二维方程直接"删掉"物品维度

把 dp[i][j] 里的 i 去掉，写成 dp[j]，转移方程在形式上变成：

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

但这里必须加上一个心照不宣的约定：dp[j - w[i]] 必须是"还没考虑过第 i 件物品"时的值。这个约定不会写在代码里，而是靠循环顺序来保证的。所以一维写法不是简单地把 i 删掉就完事，它和遍历规则是绑定的。

很多人第一次看这个方程会觉得"这不就是把 dp[i-1][j] 写成 dp[j] 吗"，字面上确实如此，但含义变了。二维里 i 是显式写出来的，你能一眼看出用的是第几层；一维里这个层号被隐藏了，它由"当前循环走到哪"隐式决定。隐藏信息一旦被忽略，bug 就来了。这也是为什么很多人二维能写对、一维就翻车——二维写错一眼能看出来，一维写错只能靠结果反推。

2.2 完整的一维模板代码

// n 件物品，背包容量 W，w[i] 重量，v[i] 价值 vector<int> dp(W + 1, 0); 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]); } } // 答案 cout << dp[W] << endl;

这两行循环就是这个问题的全部。外层 i 从 1 走到 n，表示逐个把物品纳入考虑；内层 j 从 W 倒着走到 w[i]，表示在当前物品下更新每个容量的最优值。内层循环的下界是 w[i]，因为容量比 w[i] 还小的时候根本装不下，dp[j] 保持不变，没必要进入循环。这个下界是纯优化，不影响正确性，但能让代码少跑很多无用循环。

对比一下二维代码，你会发现内层循环不再从 0 开始，而是直接从 W 往下走到 w[i]。这个细节新手常写错，要么写成从 0 到 W（方向反了），要么下界写成 0（多做无用功）。

2.3 初始化里藏着的坑

dp 数组全部初始化为 0，这是"恰好装满"和"不要求装满"两种问法的分水岭。

如果题目问的是"容量不超过 W 的最大价值"，dp 全初始化成 0 是对的，因为 dp[j] 天然表示"容量最多 j"，什么都不装也是合法状态，价值为 0。

但如果题目要求"恰好装满容量 W"，那 dp[0] = 0，其余 dp[j] = -INF。原因是：容量为 0 时价值 0 是合法的"装满"状态，其他容量在没放任何东西时是"装不满"的非法状态，用负无穷标记，只有能被转移到达的容量才会变成合法值。如果这里也全填 0，就会把"装不满"当成"价值 0 的装满"，答案直接错。求方案数的题目又是另一套：dp[0] = 1，其余为 0，因为"和为 0"本身对应一种方案。这三种初始化对应三种问法，一定要先读清楚题目问的是什么。

3. 为什么容量必须倒序遍历

3.1 正序遍历时，dp 数组的子状态被"污染"了

这是全文最核心的一节，我尽量讲得慢一点。

先假设我们不听劝，把内层循环写成正序：

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[j - w[i]] 这个量上。当 j 从小到大递增时，j - w[i] 一定小于当前的 j。既然内层是正序，那么在算 dp[j] 之前，dp[j - w[i]] 早就被算过了——而且是被同一轮（同一个 i）算过的。于是 dp[j - w[i]] 里可能已经包含了物品 i，你再用它去更新 dp[j]，物品 i 就被算了两次。

换成二维视角就更清楚了。正序遍历实际等价于：

dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])

注意加粗那一项，右边是 dp[i][...] 而不是 dp[i-1][...]。i 层依赖 i 层自己，这就是"同一件物品可以重复拿"的数学表达，正好是完全背包的转移方程。所以说，正序写出来的不是01背包，而是完全背包。很多人写一维01背包时答案偏大，就是被这个"隐形重复"坑了。

3.2 一组具体数字看"重复拿"是怎么发生的

光讲道理容易飘，拿数字推一遍最直观。

假设背包容量 W = 4，只有一件物品，重量 w = 2，价值 v = 3。因为只有一件，正确结果显然是 3（拿一次），最多也只能拿一次。

先用正序跑一遍，dp 初始为 [0, 0, 0, 0, 0]：

• j = 2：dp[2] = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3。此时 dp = [0, 0, 3, 0, 0]
• j = 3：dp[3] = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3。dp = [0, 0, 3, 3, 0]
• j = 4：dp[4] = max(dp[4], dp[2] + 3) = max(0, 3 + 3) = 6。dp = [0, 0, 3, 3, 6]

最后 dp[4] = 6。可这只有一件价值 3 的物品，怎么可能得到 6？答案揭晓：在算 dp[4] 的时候用到了 dp[2] = 3，而 dp[2] 是这一轮刚被更新的，等于已经"拿了一次"这件物品，再叠一次就成了"拿两次"。实际上重量 2 + 2 = 4 正好塞满背包，于是程序愉快地把同一件东西塞了两遍。

再看倒序，dp 初始 [0, 0, 0, 0, 0]：

• j = 4：dp[4] = max(dp[4], dp[2] + 3) = max(0, 0 + 3) = 3。dp = [0, 0, 0, 0, 3]
• j = 3：dp[3] = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3。dp = [0, 0, 0, 3, 3]
• j = 2：dp[2] = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3。dp = [0, 0, 3, 3, 3]

最后 dp[4] = 3，正确。注意这里每一步用到的 dp[j - w[i]] 都是"更小下标、还没被本轮碰过"的旧值，也就是上一层的值。这正好对应二维里的 dp[i-1][j - w[i]]，物品只被用一次，逻辑自洽。同一个方程，方向一变，结果就从 6 变回 3，差别全在读的到底是旧值还是新值。

3.3 倒序的本质：让子状态停留在上一层

把上面的现象抽象成一句话：倒序遍历时，下标大的先更新，下标小的后更新，所以当我们用到 dp[j - w[i]]（比 j 小）时，它还没被本轮修改，读到的仍然是上一层的旧值。

用依赖关系表达，倒序保证的是：

dp_new[j] = max(dp_old[j], dp_old[j - w[i]] + v[i])

而正序制造的是：

dp_new[j] = max(dp_old[j], dp_new[j - w[i]] + v[i])

一字之差，天壤之别。前者对应 01背包，后者对应完全背包。如果你哪天在纸上推完发现"怎么每件物品都能重复拿"，基本就是内层方向写反了，改一个符号就能修好。

注意：倒序只对01背包成立，完全背包恰恰要求内层正序，因为它的语义就是允许重复。方向本身没有对错，取决于你要表达哪种模型，区别就在这一个符号上。

3.4 一张表把01背包和完全背包钉死

这张表我自己贴在草稿本上贴了很久。每次写之前扫一眼，基本不会错。

4. 为什么只能先遍历物品，不能先遍历容量

4.1 循环嵌套顺序决定了"当前考虑多少件物品"

二维dp的灵魂是那个 i，也就是"前 i 件物品"这个限制。一维数组把 i 藏了起来，靠什么还原？靠外层循环的物品遍历。

当外层是物品 i 时，走到第 i 轮，dp 数组里存放的就是"只考虑前 i 件物品"的所有容量最优值。内层容量循环结束，第 i 件物品的全部决策就做完了，dp 整体从 i-1 层进阶到 i 层。这就是用循环顺序模拟物品维度，一维数组虽然没有 i 这个下标，但通过外层循环把它"模拟"了出来。

如果反过来，外层是容量 j，内层是物品 i，那么循环的第 j 轮里，dp 数组被所有物品轮流更新，可 dp 数组本身只有容量一维。"当前已经考虑了哪些物品"这个信息根本没有地方存，每一轮都是从零开始对所有物品做一次决策，物品维度彻底丢失。更直白一点：物品在外层，语义是"对每件物品，决定它在所有容量下放不放"；容量在外层，语义变成"对每个容量，把每件物品重新过一遍"，这两件事在01背包里根本不是一回事。

4.2 交换顺序后，同一件物品会被反复决策

还拿上面那件 w=2、v=3、W=4 的物品举例。交换成外层容量、内层物品：

for (int j = 0; j <= W; j++) { // 外层：容量 for (int i = 1; i <= n; i++) { // 内层：物品 if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

对 j=2：dp[2] = max(0, dp[0]+3) = 3。对 j=4：dp[4] = max(0, dp[2]+3) = 6。又出现了 6，因为 dp[2] 是这一轮外层循环早先算好的结果，带着物品的价值，再被加了一遍。而且在多物品场景下，内层遍历所有物品会让每件物品对每个容量都插一脚，最终 dp 值会明显偏高。

有人可能会想：那我把内层也改成倒序不就行了？不行。因为这里的问题不是方向，而是"物品维度无处安放"。容量循环一旦跑到外层，dp[j - w[i]] 的语义就变成了"容量更小时、已经综合考虑过所有物品的结果"，跟"前 i-1 件物品"完全不是一回事，倒序也救不了。所以方向和顺序是两个独立的约束，缺一不可。

4.3 排列还是组合：一个必须分清的分支

这里要插一句容易误伤的话。数组类问题里确实存在"先遍历容量"的写法，那是另一类问题——求方案数，而且求的是排列数。

以"凑出金额 target"为例：

• 先遍历物品、后遍历容量、容量倒序：求的是每件物品最多用一次的组合方案数（01背包方案数）。
• 先遍历物品、后遍历容量、容量正序：求的是每件物品无限次使用的组合方案数（完全背包方案数）。
• 先遍历容量、后遍历物品：求的是排列方案数，因为同一组物品的不同摆放顺序会被算成不同方案。

所以"不能先遍历容量"这句话的准确范围是：在01背包求最大价值（或01背包方案数）时不能这么做。脱离上下文说"永远不能"，是不严谨的。判断标准只有一条：你要的是组合还是排列，物品有没有顺序之分。

小技巧：如果题目强调"顺序无关"（比如选几件物品凑重量），物品放外层；如果强调"顺序有关"（比如爬楼梯式计数），才可能考虑容量放外层。判断依据是题目对"顺序"的态度，而不是死记结论。

4.4 一句能救命的记忆口诀和它的边界

把这一节压缩成一句话：物品在外层，代表"逐步把物品纳入考虑"；容量在内层，倒序是01，正序是完全。先容量后物品只在排列计数里出现，01背包的最大价值场景不适用。

我自己的习惯是每次写之前先问自己三个问题：这是不是每件物品只能用一次？我是不是在求最大价值而不是排列数？如果答案都是"是"，那就物品在外、容量在内、容量倒序，闭眼写都不会错。反过来一旦题目变成"硬币无限次"，立刻把倒序改成正序，其他不动。这套自查流程比背十遍口诀都管用，因为它逼你去想语义，而不是机械记忆。

5. 实操避坑与排查清单

5.1 常见错误速查表

写一维背包出错的地方其实高度集中，我把自己和身边人踩过的坑整理成一张表，遇到问题先对号入座。

5.2 怎么自己验证循环顺序对不对

与其背结论，不如学会自查。我给一个几乎不会出错的手工验证法：拿一件物品、一个很小的容量，在纸上把 dp 数组每次更新后的值写出来。如果发现"同一件物品被加了两次"，方向就是错的。

比如一件 w=1、v=5 的物品，容量 W=2。倒序推：dp[2] = max(0, dp[1]+5) = 5，dp[1] = max(0, dp[0]+5) = 5，最终 dp[2] = 5，正确。正序推：dp[1] = 5，dp[2] = max(0, dp[1]+5) = 10，显然错。两分钟就能验完，比对着别人的代码干瞪眼快得多。

另一个办法是把一维答案和二维暴力答案对拍。写个随机小数据生成器，n 和 W 都取 5 以内，跑几百组，只要有一组不一致就说明一维写错了。这个方法我在调一些变体题（比如带"恰好装满"或者带负数）时特别依赖，因为肉眼看不出问题，对拍一秒暴露。手推适合理解，对拍适合验证，两个配合着用效果最好。

5.3 初始化和边界的细节提醒

第一，dp 数组大小是 W + 1，不是 W，因为要表示容量 0 到 W 一共 W+1 个状态，这个差一错误极其常见，报越界或者答案差一点多半就是它。

第二，如果价值可能为负（有些题会出），"不要求装满"时 dp 全 0 就不对了，因为拿一件负价值物品还不如不拿——这种情况下要考虑题目是否允许空背包，通常题干会有说明，别想当然。

第三，物品下标从 0 还是 1 开始要统一。我习惯从 1 开始，dp[0] 留给"容量 0"，w 和 v 数组也开 n+1 大小，省得在循环里写 i-1 把自己绕晕。

第四，当容量维度较大（比如 W 到 1e5 甚至更大）时，二维数组必然爆内存，一维就是刚需，这时的循环顺序错误代价更大，务必先用小数据验证再提交。

6. 拿几道题练手：把模板用起来

6.1 最基础的01背包

题目直接给你 n、W、w[]、v[]，求最大价值。这就是模板题，直接套：

vector<int> dp(W + 1, 0); 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]); return dp[W];

这道题的价值在于验证你对"物品在外、容量倒序"的肌肉记忆。如果这题都磕磕绊绊，后面的变体只会更乱。建议先手写一遍循环，再默写一遍代码，确认自己真的记住了结构而不是记住了答案。

6.2 分割等和子集：把容量换成了目标和

LeetCode 416 给一个数组，问能不能分成两个和相等的子集。把它翻译成背包：每个数字只能用一次（是01背包），目标和是 sum/2，问能不能恰好凑出这个目标。

这里 dp 的含义变成"容量 j 能否被凑出"，转移用布尔或计数：

int target = sum / 2; vector<bool> dp(target + 1, false); dp[0] = true; for (int i = 0; i < nums.size(); i++) for (int j = target; j >= nums[i]; j--) // 依然倒序 dp[j] = dp[j] || dp[j - nums[i]]; return dp[target];

注意这里仍然是物品在外层、容量倒序，因为每个数字只能用一次。一旦把方向写成了正序，就变成"数字可以无限用"，像 [1,1] 这种本来不行的案例就会被误判成可行。

还有一个容易被忽略的剪枝：如果 sum 是奇数，直接返回 false，因为两个相等的整数和一定是偶数。这种小优化在面试里能省不少时间，也显得你考虑周全。

6.3 目标和：给转移方程加上符号

LeetCode 494 给一串数字和一个目标 S，每个数字前面可以加正号或负号，问有多少种加符号的方式能得到 S。设所有数总和为 sum，加正号的数字和为 p，则 p - (sum - p) = S，解得 p = (sum + S) / 2。于是问题变成"从数组里选若干数，使其和恰好为 p 的方案数"，又是一个01背包方案数问题。

int p = (sum + S) / 2; vector<int> dp(p + 1, 0); dp[0] = 1; // 和为0有一种方案：什么都不选 for (int i = 0; i < nums.size(); i++) for (int j = p; j >= nums[i]; j--) // 倒序，每个数只用一次 dp[j] += dp[j - nums[i]]; return dp[p];

这道题有两个要多留意的地方。一是 p 的计算结果必须是整数且非负，如果 sum + S 是奇数或者 p 超过 sum，直接返回 0，别硬算。二是 dp[0] 要初始化为 1 而不是 0，因为"和为 0"这种情况本身就对应一种方案。求方案数的题和求最大价值的题，初始化方式完全不同，这点非常容易翻车。

6.4 最后一块石头的重量 II：换个说法还是01背包

LeetCode 1049 说把一堆石头两两相撞，问最后剩的最小重量。分析下来就是把石头分成两堆让重量差最小，等价于在总和一半以内尽量装满，就是01背包求最大可装重量。套路和 416 几乎一样，只是最后返回的是 sum - 2 * dp[target]。

连着做完 416、494、1049 这三道，你会发现它们全是同一个模板的不同包装：区别只在于 dp 数组存的是"最大价值"、"布尔可达"还是"方案数"，以及初始化怎么设。循环结构一模一样，都是物品在外、容量在内、容量倒序。把这个共性看出来，以后再遇到新的01背包变体，你就知道该往哪个方向去改。

6.5 从01背包到完全背包，只改一个符号

最后做个对照实验。把上面模板的内层循环方向反过来，代码其余部分一字不动：

// 完全背包：物品无限次 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]);

就这一个方向的变化，语义从"每件最多一次"变成"每件无限次"。这也反过来说明，倒序不是随便选的，它是01背包语义在代码上的唯一正确表达。记住这个对照，面试被问到的时候可以直接答：倒序是为了让 dp[j-w[i]] 读到上一层的值，从而保证物品不被重复选取。

我自己在实际写题时的体会是，这两个循环顺序和方向的问题，看别人讲十遍不如自己拿张纸推一遍。尤其是那个只有一件物品、容量为 4 的最小例子，推完正序和倒序两次，基本就再也忘不掉了。后面再遇到求方案数、排列组合的分支，你会发现自己判断"该不该倒序、该谁在外层"的速度快很多，因为脑子里已经有那套依赖关系的画面了。