先问你一个问题如果一道01背包题目的物品数量是5000背包容量是10000你会怎么写状态数组很多人的第一反应还是dp[5001][10001]然后提交然后MLE。即使内存侥幸过关时间也往往卡在超时边缘。这种尴尬我太熟悉了——二维01背包是教材和网课里的标配讲法逻辑清晰、容易理解但到了笔试题和OJ上它往往不是最优解甚至不是可行解。今天不绕弯子直接把二维01背包和一维01背包的差异掰开揉碎从状态定义讲起把空间压缩的推导过程完整过一遍再聊初始化的坑、正序倒序的隐患以及什么时候二维写法依然不可替代。保证你以后再遇到“01背包要不要压维”这类问题心里立刻有底。1. 为什么二维写法在笔试里总被MLE先算一笔空间账1.1 两种写法一眼看懂复杂度差距到底多大先看标准形态。二维写法是vectorvectorint dp(N 1, vectorint(V 1, 0)); for (int i 1; i N; i) { for (int j 0; j V; 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]); } } }一维写法是vectorint dp(V 1, 0); for (int i 1; i N; i) { for (int j V; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }表面上只是把二维数组换成了一维数组内层循环把0 - V倒成了V - w[i]。但这两个改动背后空间复杂度从O(N*V)直接降到了O(V)而时间复杂度依然是O(N*V)。也就是说时间一分没省空间省了个量级。很多人不理解为什么要这么改其实就是因为二维数组在很多真实数据规模下根本开不出来。1.2 一亿格子的代价用具体数字看内存我给你算一笔实账。假设现在是常见的笔试规模物品数量 N 10000背包容量 V 100000。二维数组需要 (N1) x (V1) 个格子也就是约 10 亿个 int。一个 int 在多数评测机上是 4 字节10 亿个 int 大约就是 3.8GB 的内存。一台常规评测机内存上限是 256MB 或 512MB这个数组连影子都看不到编译都过不了更别说运行。哪怕把规模降到 N 2000、V 20000二维数组也要 4000 万个 int约 160MB。在某些内存限制 128MB 的老题目里照样当场死亡。但一维数组只需要 V 1 个 int也就是 20001 个 int约 80KB。差距是四到五个数量级这不是什么玄学优化而是纯粹的空间复杂度碾压。所以你应该记住这个结论只要题目里 N 和 V 的乘积明显超过 10^7就别想着开二维数组硬闯了。10^7 个 int 大约 40MB已经是很多题目的内存红线附近。如果你一看数据范围就知道 N*V 10^7那默认就该用一维写法连纠结的余地都没有。2. 二维dp[i][j]的状态定义与转移一个格子一个格子地填2.1 dp[i][j]到底在表达什么为什么非要“前i个物品”这个维度很多初学者上来就背dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])但说不清dp[i][j]是什么意思。我来用大白话讲清楚dp[i][j] 表示只考虑前 i 个物品背包容量为 j 时能拿到的最大总价值。注意这里“前 i 个”不是“前 i 个都必须选”而是“选择范围被限制在前 i 个物品里”。这个限制维度是二维写法的灵魂。为什么需要它因为决策有先后顺序——处理第 i 个物品时你面临“选或不选”两种选择而“不选”对应的状态必须来自“还没见到第 i 个物品时”的结果也就是 i-1 阶段。没有这个 i 维度你就说不清楚当前的决策是基于哪些物品做出的。2.2 转移方程的两种决策不选第i件 / 选第i件有了定义转移方程就顺理成章了。处理第 i 个物品时针对容量为 j 的背包只有两条路不选第 i 个物品那么背包里的东西就是“只考虑前 i-1 个物品、容量为 j”的最优结果即dp[i-1][j]。选第 i 个物品前提是当前容量 j 放得下这个物品即j w[i]。放进物品 i 后背包剩余容量变成j - w[i]这部分容量用于装前 i-1 个物品中的最佳组合即dp[i-1][j-w[i]]然后再加上物品 i 的价值v[i]。二选一取最大值。所以方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])初值dp[0][j] 0表示一件物品都不考虑时任何容量的背包价值都是 0。整个二维表格从第 0 行开始一行一行往下填。2.3 手工填一遍完整的dp表所有答案都藏在这张表里光说方程不够直观。我们拿一个具体例子手动填一遍你马上就能感受到这张表的节奏。假设有 4 个物品背包总容量 V 5物品编号重量 w价值 v123234345456二维dp表填完长这样行表示 i列表示 ji\j01234500000001003333200344730034574003457看几个关键格子dp[1][2] 3只考虑物品 1容量 2刚好装下物品 1价值 3。dp[2][5] 7考虑物品 1 和 2容量 5。不选物品 2是dp[1][5] 3选物品 2是dp[1][2] 4 3 4 7。所以取 7。dp[3][5] 7考虑物品 3重量 4 价值 5。走“不选”是 7走“选”是dp[2][1] 5 0 5 5所以维持 7。dp[4][5] 7物品 4 重量 5 价值 6选它的话dp[3][0] 6 6不如不选的 7。最终答案就是dp[4][5] 7。注意最后一行的每一个格子都对应某个容量下的最优解而整张表的推导过程就是反复执行“选或是不选”。你没看错二维写法本质上就是在填一张带“物品截止位置”的决策表逻辑严谨但代价就是内存。3. 压成一维的完整推导滚动数组到底滚掉了什么3.1 第i行只用第i-1行滚动压缩的数学依据为什么二维写法能压缩成一维核心观察就在转移方程本身dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])注意等号右边涉及的下标只有i-1也就是当前行只依赖上一行再往前的第 0、1、2... i-2 行一概用不上。这就意味着我们根本不需要把整张表都留在内存里只需要保留“上一行”的数据用完就丢。这个思路在动态规划里叫“滚动数组”。具体做法是开一个一维数组dp[j]在进入第 i 轮循环之前它里面保存的是第 i-1 行的所有结果。处理物品 i 时我们就在这个数组上原地更新把它变成第 i 行。下一轮物品 i1 到来之前数组里保存的恰好就是第 i 行的结果。行与行之间像滚轮一样交替覆盖所以叫“滚动”。这里的难点只有一个原地更新时必须保证用到的旧值没被覆盖掉。3.2 为什么一维必须倒序遍历一个正序就变完全背包这是全网问烂了、也最容易糊弄过去的问题。我来把因果关系讲透。假设数组dp[j]当前保存的是第 i-1 行的值。我们要更新dp[j]需要参考dp[j - w[i]]。由于j - w[i] j如果内层循环是从小到大正序遍历那么当 j 走到某个值时dp[j - w[i]]已经在本次循环里被更新过了——它已经变成了第 i 行的值而不是第 i-1 行的旧值。问题就出在这。第 i 行的dp[j - w[i]]本身可能已经被“选物品 i”这个决策影响过你再拿它去更新dp[j]等于在一条决策链里把物品 i 用了两次、三次甚至更多次。这正好就是完全背包的语义每个物品可以无限取。所以正序遍历一维数组不是“小错”而是直接换了一个背包模型答案通常会明显偏大。倒序遍历就不存在这个问题。j 从 V 往 w[i] 递减每次更新dp[j]时j - w[i]比 j 小但比 j 大的那些容量已经被更新比 j 小的容量还停留在第 i-1 行的旧值。而我们要的恰恰就是旧值。这样每个物品在当前轮只能被纳入一次完美保留 01 背包的“每件最多选一次”约束。我用一个生活场景类比这笔旧账就好比你钱包里的余额今天每笔消费都需要参考“昨天结算后的余额”而不是“今天已经花过几笔的余额”。如果你正着算后面的消费会拿着已经更新过的余额继续消费等于同一天的钱反复花了好几次。3.3 标准代码与一句自检口诀一维标准写法再贴一遍这次加上注释vectorint dp(V 1, 0); for (int i 1; i N; i) { for (int j V; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }Python 版本核心循环长这样dp [0] * (V 1) for i in range(1, N 1): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])我自己总结了一句自检口诀分享给你容量倒序物品在外状态只看上一轮旧值不覆盖。每次写完一维背包代码先对一对这句话。如果内层不是倒序、或者内外层顺序反了十有八九要出事。4. 三个最经典的翻车现场MLE、正序、内外层交换4.1 翻车现场一MLE不是玄学是可以提前算出来的我见过太多人写二维dp数据范围也不看上来就int dp[10005][10005]编译倒是过了一跑直接 MLE。这种错误不是一个“把数组改成一维”就能糊弄过去的你必须在动手之前就对内存有感知。方法很简单把 N1 乘以 V1再乘以 4int字节数换算成 MB。公式内存占用(MB) ≈ (N1) * (V1) * 4 / 1024 / 1024举个例子N 5000、V 10000二维数组大约 5000 * 10001 * 4 / 1048576 ≈ 190MB。很多题目内存限制是 256MB这看起来好像能过其实很悬如果你再开几个辅助数组立刻爆。N 10000、V 100000 我前面算过3.8GB直接没戏。所以看到大范围第一反应就应该是能不能压维。4.2 翻车现场二正序/倒序写反答案莫名偏大有些朋友背模板把一维背包的内层循环从V到w[i]写成了w[i]到V结果也没报错就是答案不对。跑对拍就会发现答案比正确答案大了一圈。这就是正序遍历的典型症状。因为每个物品可以被“复选”价值被反复累加最优结果自然膨胀。更迷惑的是某些小样例它也能跑出正确结果比如物品重量都很大、容量很小的时候同一轮里能被复选的次数有限甚至恰好踩不出差异。这就是为什么很多人错在正序上还一脸茫然。如果你想亲眼确认这个现象可以在本地把内层循环改成正序跑一遍前面的样例然后把自己写背包时的 debug 输出加一行cout dp[j] ;你会看到同一轮循环里dp[4]、dp[5]这种大容量格子的值出现了“同物品累加”的痕迹。4.3 翻车现场三内外层循环交换状态含义直接崩坏还有一类错误是把容量循环放外层、物品循环放内层写成for (int j V; j 0; --j) { for (int i 1; i N; i) { if (j w[i]) dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这个写法从二维视角看完全破坏了“阶段”概念。二维写法之所以把物品 i 放外层是因为每一行代表一个明确的决策阶段容量 j 只是这个阶段内部的状态枚举。一旦把容量放外层你面对容量 j 时内层把所有物品都过了一遍某个物品可能在多个容量层之间反复影响结果状态转移不再有“前 i 个物品”这个清晰边界。结果既不是 01 背包也不是完全背包而是语义混乱的“伪背包”答案不可预测。我给你的建议是只记一种结构——物品在外层容量在倒序内层。不要试图通过交换循环来优化什么01背包这个模型的结构就是这么规定的理解它为什么这样规定比另辟蹊径重要得多。4.4 怎么快速给自己debug暴力枚举做基准写背包题最容易出现的困境是“错了但不知道错在哪”。我的习惯是写一个纯暴力枚举作对照。对于 N 很小的情况直接递归枚举所有物品子集算每个子集的总重量和总价值找出合法最大价值。然后把暴力结果和背包结果对拍。对拍代码不需要漂亮能用就行int ans 0; for (int mask 0; mask (1 N); mask) { int sumW 0, sumV 0; for (int i 0; i N; i) { if (mask (1 i)) { sumW w[i]; sumV v[i]; } } if (sumW V) ans max(ans, sumV); }这个ans就是答案的基准值。背包解不等于它就回去检查循环结构、初始化、下标。这个方法我用了很多年比对着题解瞎猜效率高太多。5. 初始化是个精细活恰好装满、方案数与LeetCode变种5.1 三种初始化的语义随便装、恰好装满、求方案数同样是一维写法初始化的不同会直接改变题目语义。刷题时很多隐藏条件就藏在这一步。第一种不要求装满背包。也就是只要总重量不超过容量即可。初始化一律填 0。因为容量没用完也是合法的dp[j] 至少可以是 0什么都不装。上面所有例子的初始化都是这种。第二种要求恰好装满背包。这时容量没被完全利用的状态必须视为非法。做法是dp[0] 0其余dp[j] -INF用-1e9这种足够小的数。转移时非法的-INF加上任何价值还是无穷小max 天然不会选中它们。最终如果dp[V]还是负数就说明无法恰好装满。为什么需要这种区分举个实际例子题目问“容量为 V 的背包能否恰好装满”如果初始化全是 0那你可能拿一个没装满的方案当答案如果初始化带-INF非法状态天然被过滤。第三种求方案数。典型初始化是dp[0] 1其余为 0。转移方程从max变成累加dp[j] dp[j - w[i]]。dp[j]的语义变成“凑出容量 j 的方案数”。dp[0]1表示容量 0 只有一种方案——什么都不选。5.2 LeetCode 416判断能不能装满给你举两个实战题加深印象。LeetCode 416“分割等和子集”题意是判断一个数组能否分成两个和相等的子集。等价于能否从数组里选出一些数字使它们的和等于总和的一半target。这就是“恰好装满”版本只是价值等于重量。用一维布尔数组写法vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; --j) { dp[j] dp[j] || dp[j - num]; } }注意这里同样必须倒序。如果正序同一个数字就会被重复用比如nums [2]、target 4正序会让dp[2]true去更新dp[4]true看起来好像能凑出 4但实际只有一个 2根本凑不出来。这就是典型正序翻车。5.3 LeetCode 494恰好装满的方案数LeetCode 494“目标和”可以把数字分成正数部分和负数部分。设正数部分和为 P则P - (sum - P) target所以P (sum target) / 2。问题变成从数组里选一些数字使和恰好为 P问方案数。DP 写法vectorint dp(P 1, 0); dp[0] 1; for (int num : nums) { for (int j P; j num; --j) { dp[j] dp[j - num]; } }这里有几个易错点(sum target)必须是偶数否则无解target绝对值不能大于sum。这些条件不满足直接返回 0不要硬算。初始化dp[0]1是方案数题的关键每多一个numdp[j]就把“不选 num”的旧方案数和“选 num”的新方案数加起来。5.4 初始化取舍速查表我把常见变种整理成一张表方便你写之前一眼锁定初始化题目语义dp[0]其他dp[j]转移操作典型题目最大价值不要求装满00max经典01背包最大价值恰好装满0-INFmax凑硬币最大值之类可行性判断truefalse或运算LeetCode 416方案数统计10累加LeetCode 494一句话初始化决定状态合法性转移决定状态演进方式。二者分开理解变种题就不会乱。6. 二维仍然不可替代的三个场景回推方案、二维费用、记忆化6.1 场景一题目要你输出具体选了哪些东西一维滚动数组省空间的代价是中间行的信息被覆盖最终只知道最大价值是dp[V]但不知道是哪几个物品贡献出来的。如果题目要求输出具体方案你就不能只压成一维。标准做法是保留完整二维dp表或者额外维护一个choice[i][j]数组记录dp[i][j]这一步是“不选物品 i”还是“选了物品 i”。回推时从(N, V)倒着走如果choice[i][j]表明选了物品 i就记录该物品然后跳到(i-1, j-w[i])否则跳到(i-1, j)。在这种场景下完整表格本身就是“决策路径”的存档滚动数组只是把存档丢掉了。所以我不建议为了省空间盲目压维先看清楚题目的输出要求。6.2 场景二二维费用背包这个“二维”跟本文不是一回事这里必须澄清一个概念坑。网上一搜“二维01背包”有时候指的压根不是“二维dp数组”而是“二维费用背包”——每个物品同时消耗两种资源比如重量和体积背包有两个容量上限。状态是dp[i][j]含义是“在重量不超过 i、体积不超过 j 的前提下能拿到的最大价值”。这个模型的循环结构依然是物品在外层两个容量维度都要求倒序for (int k 1; k N; k) { for (int i maxWeight; i weight[k]; --i) { for (int j maxVol; j vol[k]; --j) { dp[i][j] max(dp[i][j], dp[i - weight[k]][j - vol[k]] value[k]); } } }LeetCode 474“一和零”就是典型例子每个字符串消耗 0 的个数和 1 的个数问你最多能拼出多少个字符串。这里的“二维”是指两种容量维度并存和本文主题“二维数组 vs 一维数组的01背包”是两码事。面试时如果别人说“二维背包”你最好追问一句是“二维dp表格”还是“二维费用”避免双方鸡同鸭讲。6.3 场景三记忆化搜索与状态压缩DP还有一类场景二维数组不是为了表格美观而是因为递归搜索天然带有“位置 容量”两个状态维度。比如用记忆化搜索写背包int dfs(int i, int j) { if (i 0 || j 0) return 0; if (memo[i][j] ! -1) return memo[i][j]; return memo[i][j] max(dfs(i - 1, j), dfs(i - 1, j - w[i]) v[i]); }这里的memo[i][j]就是二维表只是用递归触达顺序去填充本质和二维迭代dp一样。这种写法在需要记录大量中间状态、或者状态转移带额外条件时更自然代价同样是内存。另外一些状态压缩DP比如需要保留每个子集和容量组合的结果也必然要开二维或更大的表这时候强行“压维”就没意义了。所以我的建议是二维写法不是永远劣势它适合“需要回溯路径”“状态维度天然分裂”“递归记忆化”这三类场景而一维写法适合“只要最终价值/可行性/方案数不要过程”的绝大多数竞赛题。两者各司其职真正的高手不是只会背一种而是拿到题先问自己一个问题“这道题要我输出价值还是要我输出路径”这个问题想清楚了选哪种写法根本不用犹豫。最后再分享一个小经验。我刚开始学背包的时候总觉得一维写法是某种“高深魔法”后来亲手把二维表格画出来、又模拟了压缩过程才明白它只是“只保留上一行”的工程化取舍。建议你也别急着背代码拿一张纸、四个物品从二维表填到一维滚动把每一轮数组的内容都写出来对照一次。这个过程花不了半小时但能帮你把“为什么倒序”“为什么外层是物品”这些细节焊死在脑子里。之后遇到402、416、494这些变种题你大概率一眼就能看出该套哪套模板、改哪一行初始化。
01背包压维实战：从二维MLE到一维倒序，彻底解决空间与效率问题
先问你一个问题如果一道01背包题目的物品数量是5000背包容量是10000你会怎么写状态数组很多人的第一反应还是dp[5001][10001]然后提交然后MLE。即使内存侥幸过关时间也往往卡在超时边缘。这种尴尬我太熟悉了——二维01背包是教材和网课里的标配讲法逻辑清晰、容易理解但到了笔试题和OJ上它往往不是最优解甚至不是可行解。今天不绕弯子直接把二维01背包和一维01背包的差异掰开揉碎从状态定义讲起把空间压缩的推导过程完整过一遍再聊初始化的坑、正序倒序的隐患以及什么时候二维写法依然不可替代。保证你以后再遇到“01背包要不要压维”这类问题心里立刻有底。1. 为什么二维写法在笔试里总被MLE先算一笔空间账1.1 两种写法一眼看懂复杂度差距到底多大先看标准形态。二维写法是vectorvectorint dp(N 1, vectorint(V 1, 0)); for (int i 1; i N; i) { for (int j 0; j V; 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]); } } }一维写法是vectorint dp(V 1, 0); for (int i 1; i N; i) { for (int j V; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }表面上只是把二维数组换成了一维数组内层循环把0 - V倒成了V - w[i]。但这两个改动背后空间复杂度从O(N*V)直接降到了O(V)而时间复杂度依然是O(N*V)。也就是说时间一分没省空间省了个量级。很多人不理解为什么要这么改其实就是因为二维数组在很多真实数据规模下根本开不出来。1.2 一亿格子的代价用具体数字看内存我给你算一笔实账。假设现在是常见的笔试规模物品数量 N 10000背包容量 V 100000。二维数组需要 (N1) x (V1) 个格子也就是约 10 亿个 int。一个 int 在多数评测机上是 4 字节10 亿个 int 大约就是 3.8GB 的内存。一台常规评测机内存上限是 256MB 或 512MB这个数组连影子都看不到编译都过不了更别说运行。哪怕把规模降到 N 2000、V 20000二维数组也要 4000 万个 int约 160MB。在某些内存限制 128MB 的老题目里照样当场死亡。但一维数组只需要 V 1 个 int也就是 20001 个 int约 80KB。差距是四到五个数量级这不是什么玄学优化而是纯粹的空间复杂度碾压。所以你应该记住这个结论只要题目里 N 和 V 的乘积明显超过 10^7就别想着开二维数组硬闯了。10^7 个 int 大约 40MB已经是很多题目的内存红线附近。如果你一看数据范围就知道 N*V 10^7那默认就该用一维写法连纠结的余地都没有。2. 二维dp[i][j]的状态定义与转移一个格子一个格子地填2.1 dp[i][j]到底在表达什么为什么非要“前i个物品”这个维度很多初学者上来就背dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])但说不清dp[i][j]是什么意思。我来用大白话讲清楚dp[i][j] 表示只考虑前 i 个物品背包容量为 j 时能拿到的最大总价值。注意这里“前 i 个”不是“前 i 个都必须选”而是“选择范围被限制在前 i 个物品里”。这个限制维度是二维写法的灵魂。为什么需要它因为决策有先后顺序——处理第 i 个物品时你面临“选或不选”两种选择而“不选”对应的状态必须来自“还没见到第 i 个物品时”的结果也就是 i-1 阶段。没有这个 i 维度你就说不清楚当前的决策是基于哪些物品做出的。2.2 转移方程的两种决策不选第i件 / 选第i件有了定义转移方程就顺理成章了。处理第 i 个物品时针对容量为 j 的背包只有两条路不选第 i 个物品那么背包里的东西就是“只考虑前 i-1 个物品、容量为 j”的最优结果即dp[i-1][j]。选第 i 个物品前提是当前容量 j 放得下这个物品即j w[i]。放进物品 i 后背包剩余容量变成j - w[i]这部分容量用于装前 i-1 个物品中的最佳组合即dp[i-1][j-w[i]]然后再加上物品 i 的价值v[i]。二选一取最大值。所以方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])初值dp[0][j] 0表示一件物品都不考虑时任何容量的背包价值都是 0。整个二维表格从第 0 行开始一行一行往下填。2.3 手工填一遍完整的dp表所有答案都藏在这张表里光说方程不够直观。我们拿一个具体例子手动填一遍你马上就能感受到这张表的节奏。假设有 4 个物品背包总容量 V 5物品编号重量 w价值 v123234345456二维dp表填完长这样行表示 i列表示 ji\j01234500000001003333200344730034574003457看几个关键格子dp[1][2] 3只考虑物品 1容量 2刚好装下物品 1价值 3。dp[2][5] 7考虑物品 1 和 2容量 5。不选物品 2是dp[1][5] 3选物品 2是dp[1][2] 4 3 4 7。所以取 7。dp[3][5] 7考虑物品 3重量 4 价值 5。走“不选”是 7走“选”是dp[2][1] 5 0 5 5所以维持 7。dp[4][5] 7物品 4 重量 5 价值 6选它的话dp[3][0] 6 6不如不选的 7。最终答案就是dp[4][5] 7。注意最后一行的每一个格子都对应某个容量下的最优解而整张表的推导过程就是反复执行“选或是不选”。你没看错二维写法本质上就是在填一张带“物品截止位置”的决策表逻辑严谨但代价就是内存。3. 压成一维的完整推导滚动数组到底滚掉了什么3.1 第i行只用第i-1行滚动压缩的数学依据为什么二维写法能压缩成一维核心观察就在转移方程本身dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])注意等号右边涉及的下标只有i-1也就是当前行只依赖上一行再往前的第 0、1、2... i-2 行一概用不上。这就意味着我们根本不需要把整张表都留在内存里只需要保留“上一行”的数据用完就丢。这个思路在动态规划里叫“滚动数组”。具体做法是开一个一维数组dp[j]在进入第 i 轮循环之前它里面保存的是第 i-1 行的所有结果。处理物品 i 时我们就在这个数组上原地更新把它变成第 i 行。下一轮物品 i1 到来之前数组里保存的恰好就是第 i 行的结果。行与行之间像滚轮一样交替覆盖所以叫“滚动”。这里的难点只有一个原地更新时必须保证用到的旧值没被覆盖掉。3.2 为什么一维必须倒序遍历一个正序就变完全背包这是全网问烂了、也最容易糊弄过去的问题。我来把因果关系讲透。假设数组dp[j]当前保存的是第 i-1 行的值。我们要更新dp[j]需要参考dp[j - w[i]]。由于j - w[i] j如果内层循环是从小到大正序遍历那么当 j 走到某个值时dp[j - w[i]]已经在本次循环里被更新过了——它已经变成了第 i 行的值而不是第 i-1 行的旧值。问题就出在这。第 i 行的dp[j - w[i]]本身可能已经被“选物品 i”这个决策影响过你再拿它去更新dp[j]等于在一条决策链里把物品 i 用了两次、三次甚至更多次。这正好就是完全背包的语义每个物品可以无限取。所以正序遍历一维数组不是“小错”而是直接换了一个背包模型答案通常会明显偏大。倒序遍历就不存在这个问题。j 从 V 往 w[i] 递减每次更新dp[j]时j - w[i]比 j 小但比 j 大的那些容量已经被更新比 j 小的容量还停留在第 i-1 行的旧值。而我们要的恰恰就是旧值。这样每个物品在当前轮只能被纳入一次完美保留 01 背包的“每件最多选一次”约束。我用一个生活场景类比这笔旧账就好比你钱包里的余额今天每笔消费都需要参考“昨天结算后的余额”而不是“今天已经花过几笔的余额”。如果你正着算后面的消费会拿着已经更新过的余额继续消费等于同一天的钱反复花了好几次。3.3 标准代码与一句自检口诀一维标准写法再贴一遍这次加上注释vectorint dp(V 1, 0); for (int i 1; i N; i) { for (int j V; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }Python 版本核心循环长这样dp [0] * (V 1) for i in range(1, N 1): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])我自己总结了一句自检口诀分享给你容量倒序物品在外状态只看上一轮旧值不覆盖。每次写完一维背包代码先对一对这句话。如果内层不是倒序、或者内外层顺序反了十有八九要出事。4. 三个最经典的翻车现场MLE、正序、内外层交换4.1 翻车现场一MLE不是玄学是可以提前算出来的我见过太多人写二维dp数据范围也不看上来就int dp[10005][10005]编译倒是过了一跑直接 MLE。这种错误不是一个“把数组改成一维”就能糊弄过去的你必须在动手之前就对内存有感知。方法很简单把 N1 乘以 V1再乘以 4int字节数换算成 MB。公式内存占用(MB) ≈ (N1) * (V1) * 4 / 1024 / 1024举个例子N 5000、V 10000二维数组大约 5000 * 10001 * 4 / 1048576 ≈ 190MB。很多题目内存限制是 256MB这看起来好像能过其实很悬如果你再开几个辅助数组立刻爆。N 10000、V 100000 我前面算过3.8GB直接没戏。所以看到大范围第一反应就应该是能不能压维。4.2 翻车现场二正序/倒序写反答案莫名偏大有些朋友背模板把一维背包的内层循环从V到w[i]写成了w[i]到V结果也没报错就是答案不对。跑对拍就会发现答案比正确答案大了一圈。这就是正序遍历的典型症状。因为每个物品可以被“复选”价值被反复累加最优结果自然膨胀。更迷惑的是某些小样例它也能跑出正确结果比如物品重量都很大、容量很小的时候同一轮里能被复选的次数有限甚至恰好踩不出差异。这就是为什么很多人错在正序上还一脸茫然。如果你想亲眼确认这个现象可以在本地把内层循环改成正序跑一遍前面的样例然后把自己写背包时的 debug 输出加一行cout dp[j] ;你会看到同一轮循环里dp[4]、dp[5]这种大容量格子的值出现了“同物品累加”的痕迹。4.3 翻车现场三内外层循环交换状态含义直接崩坏还有一类错误是把容量循环放外层、物品循环放内层写成for (int j V; j 0; --j) { for (int i 1; i N; i) { if (j w[i]) dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这个写法从二维视角看完全破坏了“阶段”概念。二维写法之所以把物品 i 放外层是因为每一行代表一个明确的决策阶段容量 j 只是这个阶段内部的状态枚举。一旦把容量放外层你面对容量 j 时内层把所有物品都过了一遍某个物品可能在多个容量层之间反复影响结果状态转移不再有“前 i 个物品”这个清晰边界。结果既不是 01 背包也不是完全背包而是语义混乱的“伪背包”答案不可预测。我给你的建议是只记一种结构——物品在外层容量在倒序内层。不要试图通过交换循环来优化什么01背包这个模型的结构就是这么规定的理解它为什么这样规定比另辟蹊径重要得多。4.4 怎么快速给自己debug暴力枚举做基准写背包题最容易出现的困境是“错了但不知道错在哪”。我的习惯是写一个纯暴力枚举作对照。对于 N 很小的情况直接递归枚举所有物品子集算每个子集的总重量和总价值找出合法最大价值。然后把暴力结果和背包结果对拍。对拍代码不需要漂亮能用就行int ans 0; for (int mask 0; mask (1 N); mask) { int sumW 0, sumV 0; for (int i 0; i N; i) { if (mask (1 i)) { sumW w[i]; sumV v[i]; } } if (sumW V) ans max(ans, sumV); }这个ans就是答案的基准值。背包解不等于它就回去检查循环结构、初始化、下标。这个方法我用了很多年比对着题解瞎猜效率高太多。5. 初始化是个精细活恰好装满、方案数与LeetCode变种5.1 三种初始化的语义随便装、恰好装满、求方案数同样是一维写法初始化的不同会直接改变题目语义。刷题时很多隐藏条件就藏在这一步。第一种不要求装满背包。也就是只要总重量不超过容量即可。初始化一律填 0。因为容量没用完也是合法的dp[j] 至少可以是 0什么都不装。上面所有例子的初始化都是这种。第二种要求恰好装满背包。这时容量没被完全利用的状态必须视为非法。做法是dp[0] 0其余dp[j] -INF用-1e9这种足够小的数。转移时非法的-INF加上任何价值还是无穷小max 天然不会选中它们。最终如果dp[V]还是负数就说明无法恰好装满。为什么需要这种区分举个实际例子题目问“容量为 V 的背包能否恰好装满”如果初始化全是 0那你可能拿一个没装满的方案当答案如果初始化带-INF非法状态天然被过滤。第三种求方案数。典型初始化是dp[0] 1其余为 0。转移方程从max变成累加dp[j] dp[j - w[i]]。dp[j]的语义变成“凑出容量 j 的方案数”。dp[0]1表示容量 0 只有一种方案——什么都不选。5.2 LeetCode 416判断能不能装满给你举两个实战题加深印象。LeetCode 416“分割等和子集”题意是判断一个数组能否分成两个和相等的子集。等价于能否从数组里选出一些数字使它们的和等于总和的一半target。这就是“恰好装满”版本只是价值等于重量。用一维布尔数组写法vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; --j) { dp[j] dp[j] || dp[j - num]; } }注意这里同样必须倒序。如果正序同一个数字就会被重复用比如nums [2]、target 4正序会让dp[2]true去更新dp[4]true看起来好像能凑出 4但实际只有一个 2根本凑不出来。这就是典型正序翻车。5.3 LeetCode 494恰好装满的方案数LeetCode 494“目标和”可以把数字分成正数部分和负数部分。设正数部分和为 P则P - (sum - P) target所以P (sum target) / 2。问题变成从数组里选一些数字使和恰好为 P问方案数。DP 写法vectorint dp(P 1, 0); dp[0] 1; for (int num : nums) { for (int j P; j num; --j) { dp[j] dp[j - num]; } }这里有几个易错点(sum target)必须是偶数否则无解target绝对值不能大于sum。这些条件不满足直接返回 0不要硬算。初始化dp[0]1是方案数题的关键每多一个numdp[j]就把“不选 num”的旧方案数和“选 num”的新方案数加起来。5.4 初始化取舍速查表我把常见变种整理成一张表方便你写之前一眼锁定初始化题目语义dp[0]其他dp[j]转移操作典型题目最大价值不要求装满00max经典01背包最大价值恰好装满0-INFmax凑硬币最大值之类可行性判断truefalse或运算LeetCode 416方案数统计10累加LeetCode 494一句话初始化决定状态合法性转移决定状态演进方式。二者分开理解变种题就不会乱。6. 二维仍然不可替代的三个场景回推方案、二维费用、记忆化6.1 场景一题目要你输出具体选了哪些东西一维滚动数组省空间的代价是中间行的信息被覆盖最终只知道最大价值是dp[V]但不知道是哪几个物品贡献出来的。如果题目要求输出具体方案你就不能只压成一维。标准做法是保留完整二维dp表或者额外维护一个choice[i][j]数组记录dp[i][j]这一步是“不选物品 i”还是“选了物品 i”。回推时从(N, V)倒着走如果choice[i][j]表明选了物品 i就记录该物品然后跳到(i-1, j-w[i])否则跳到(i-1, j)。在这种场景下完整表格本身就是“决策路径”的存档滚动数组只是把存档丢掉了。所以我不建议为了省空间盲目压维先看清楚题目的输出要求。6.2 场景二二维费用背包这个“二维”跟本文不是一回事这里必须澄清一个概念坑。网上一搜“二维01背包”有时候指的压根不是“二维dp数组”而是“二维费用背包”——每个物品同时消耗两种资源比如重量和体积背包有两个容量上限。状态是dp[i][j]含义是“在重量不超过 i、体积不超过 j 的前提下能拿到的最大价值”。这个模型的循环结构依然是物品在外层两个容量维度都要求倒序for (int k 1; k N; k) { for (int i maxWeight; i weight[k]; --i) { for (int j maxVol; j vol[k]; --j) { dp[i][j] max(dp[i][j], dp[i - weight[k]][j - vol[k]] value[k]); } } }LeetCode 474“一和零”就是典型例子每个字符串消耗 0 的个数和 1 的个数问你最多能拼出多少个字符串。这里的“二维”是指两种容量维度并存和本文主题“二维数组 vs 一维数组的01背包”是两码事。面试时如果别人说“二维背包”你最好追问一句是“二维dp表格”还是“二维费用”避免双方鸡同鸭讲。6.3 场景三记忆化搜索与状态压缩DP还有一类场景二维数组不是为了表格美观而是因为递归搜索天然带有“位置 容量”两个状态维度。比如用记忆化搜索写背包int dfs(int i, int j) { if (i 0 || j 0) return 0; if (memo[i][j] ! -1) return memo[i][j]; return memo[i][j] max(dfs(i - 1, j), dfs(i - 1, j - w[i]) v[i]); }这里的memo[i][j]就是二维表只是用递归触达顺序去填充本质和二维迭代dp一样。这种写法在需要记录大量中间状态、或者状态转移带额外条件时更自然代价同样是内存。另外一些状态压缩DP比如需要保留每个子集和容量组合的结果也必然要开二维或更大的表这时候强行“压维”就没意义了。所以我的建议是二维写法不是永远劣势它适合“需要回溯路径”“状态维度天然分裂”“递归记忆化”这三类场景而一维写法适合“只要最终价值/可行性/方案数不要过程”的绝大多数竞赛题。两者各司其职真正的高手不是只会背一种而是拿到题先问自己一个问题“这道题要我输出价值还是要我输出路径”这个问题想清楚了选哪种写法根本不用犹豫。最后再分享一个小经验。我刚开始学背包的时候总觉得一维写法是某种“高深魔法”后来亲手把二维表格画出来、又模拟了压缩过程才明白它只是“只保留上一行”的工程化取舍。建议你也别急着背代码拿一张纸、四个物品从二维表填到一维滚动把每一轮数组的内容都写出来对照一次。这个过程花不了半小时但能帮你把“为什么倒序”“为什么外层是物品”这些细节焊死在脑子里。之后遇到402、416、494这些变种题你大概率一眼就能看出该套哪套模板、改哪一行初始化。
