0-1背包这个题我给不同的人讲过不下十遍几乎每一轮都会卡在同一个地方二维数组写得清清楚楚一看就懂压成一维之后脑子就开始打结尤其卡在那个倒序循环上——为什么背包容量一定要从大到小跑我把它改成正序跑出来的数居然也像模像样甚至有时候还更大看着更优。再往下问一层为什么一维写法只能先遍历物品、不能先遍历背包容量绝大多数人就答不上来了只能背结论。这篇就把这件事从头到尾拆开讲从二维dp怎么推出来到一维滚动数组到底省掉了什么信息再到倒序遍历的每一步实际读的是哪个旧值最后把先遍历背包为什么必然出错用可复现的数据摆出来。看完之后你不需要再背任何结论0-1背包问题、一维dp数组、倒序遍历背包、先遍历背包、先遍历物品这几件事会连成一条完整的因果链。1. 从题目到模型0-1背包到底在问什么1.1 三个约束条件先摆清楚0-1背包的标准描述是给定 n 件物品第 i 件物品的重量是w[i]、价值是v[i]再给一个承重上限为V的背包问在总重量不超过V的前提下能装走的最大总价值是多少。这段话里有三个不能含糊的约束我在看别人的代码时经常发现有人只记住了第一个每件物品最多取一次取就是 1不取就是 0这正是0-1这个名字的来源也是它和完全背包、多重背包最根本的分界线。背包的重量上限是V累计重量不能超但不要求装满装到 3.7kg 和装到 4.0kg 在最大价值这个目标下没有区别。目标是总价值最大不是重量最大也不是物品个数最多。这三条看着平淡实际决定了后面所有代码细节。比如第二条直接决定了初始化怎么写——不要求装满时dp数组全填 0 就行如果题目改成恰好装满背包时的最大价值那初始化就必须是dp[0] 0、其余位置填负无穷否则你会得到一个没装满但价值很大的错误答案。很多人栽在这上面把一道恰好装满的题按不要求装满写了样例还过了因为样例恰好就是能装满的。1.2 暴力搜索为什么扛不住最直觉的做法是枚举每件物品选或不选一共 2^n 种组合逐个检查重量、记录最大价值。n 等于 20 的时候是 100 万种组合还能忍n 等于 30 就是 10 亿基本没戏。而真实的业务场景里 n 到几百、上千是常态比如资源调度里从一堆任务里挑哪些执行能产出最大收益候选集合动辄上千2^n 这种量级连想都不用想。更要命的是这 2^n 种组合里有大量重复的子结构。举个具体例子三件物品重量分别是 1、2、3价值分别是 10、20、30。组合选物品1和物品3和组合选物品2……在重量维度上经常撞到同一个剩余容量后面能做的决策完全一样但暴力搜索会把这些子问题重新算一遍又一遍。这就是典型的重叠子问题也正是动态规划要切进去的地方。1.3 为什么贪心在这里会翻车有人会想那我按性价比排序优先拿价值密度最高的不就行了不行。举个反例V 4物品 A 重量 3、价值 30密度 10物品 B 和 C 重量都是 2、价值各 19密度 9.5。贪心先拿 A占了 3kg剩 1kg 什么都放不下总价值 30。而最优解是拿 B 和 C重量 4价值 38。贪心在每一步局部看起来都对合起来就错了因为背包问题里装不满的零头会直接吃掉后面的机会。这就是为什么必须用动态规划把剩余容量这个维度的所有可能性都考虑进去。0-1背包是典型的 NPC 问题但它有一个非常好的性质重量维度是整数且上界有限。只要V不是天文数字我们就能把容量作为状态维度展开把指数级的组合搜索压到O(n × V)。这个用容量换时间的取舍是整个算法成立的根基。2. 二维dp是怎么一步步推出来的2.1 阶段、状态、决策三件套动态规划的三要素在背包问题上对应得特别干净阶段处理到第几件物品了用i表示从 0 到 n。状态dp[i][j]表示只考虑前 i 件物品、背包容量恰好为 j不要求装满指的是容量上限为 j时能取得的最大价值。决策第 i 件物品取还是不取。状态定义里最容易出错的是恰好为 j和不超过 j的区别。我建议初学者统一按容量上限为 j来理解dp[i][j]的含义就是前 i 件物品在容量不超过 j 的情况下能拿到的最大价值。这样初始化全 0 就天然成立一件都不拿任何容量下的最大价值都是 0。无后效性也就体现在这里一旦我决定好了前 i 件物品怎么处理后面第 i1 件物品怎么选只跟还剩多少容量有关跟前 i 件具体选了哪几件无关。这个性质是压缩空间的前提记住它后面一维数组的推导全靠它。2.2 状态转移方程与边界对第 i 件物品下标从 0 开始第 i 件对应w[i]、v[i]只有两种选择不取它最大值就是从上一阶段继承dp[i-1][j]。取它前提是j w[i]那么最大值是dp[i-1][j - w[i]] v[i]。这里的关键在于取的时候查的是dp[i-1][...]而不是dp[i][...]因为每件物品只能用一次取了第 i 件之后剩余容量只能在前 i-1 件里做文章绝不能再去考虑第 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]边界条件是dp[0][j] 0也就是一件物品都不考虑时任何容量的最大价值都是 0。还有一行隐藏的边界j w[i]时第二项不存在直接继承上一行。这两条看起来简单但它们决定了循环里if判断怎么写。2.3 用一组小数据手工跑一遍二维表空谈公式没用我们拿一组数据把整张表算出来后面一维的对比全靠这张表。物品与价值编号重量 w价值 v物品0115物品1320物品2430背包容量V 4。第一行只考虑物品0容量 0 拿不了容量 1、2、3、4 都能拿物品0。dp[0][j] 0, 15, 15, 15, 15第二行加上物品1重量3价值20j 2时j 3继承dp[0][2] 15j 3时max(dp[0][3]15, dp[0][0]2020) 20j 4时max(dp[0][4]15, dp[0][1]2035) 35dp[1][j] 0, 15, 15, 20, 35第三行加上物品2重量4价值30j 3时j 4继承dp[1][3] 20j 4时max(dp[1][4]35, dp[1][0]3030) 35dp[2][j] 0, 15, 15, 20, 35最终答案是35对应取物品0和物品1重量 134价值 152035。注意物品2虽然单价最高但塞进去之后就装不下别的了反而亏。这张表后面会被反复引用一维数组正确跑完一遍的结果必须逐格等于这张二维表的最后一行。这是判断一维写法对不对的唯一硬标准也是对拍测试的对照物。作者自己写代码的时候如果一时想不通某段循环为什么那样写就把这张表拿出来比一比比空想快得多。3. 从二维压到一维滚动数组到底省了什么3.1 二维转一维的观察点盯着上面那张表看三十秒你会发现一个很重要的规律算dp[i][j]的时候用到的只有dp[i-1][j]和dp[i-1][j-w[i]]全部来自上一行。前一行的数据在算完当前行之后就没用了再往上第 i-2 行更是彻底作废。既然只用上一行那开 n1 行就是纯浪费。一个自然的想法是能不能只留一行在这一行上就地更新把上一行的值覆盖掉可以但有个前提覆盖的时机必须保证你还没用到这个位置上的旧值。这就是后面所有讨论的核心矛盾。3.2 一维数组每一轮代表什么压成一维之后dp[j]的含义需要重新说清楚否则一定会绕晕。准确的说法是在第 i 轮循环也就是处理完前 i 件物品结束之后dp[j]表示前 i 件物品在容量上限 j 下能取得的最大价值。而在第 i 轮循环进行过程中dp[j]里装的是上一层前 i-1 件物品的答案只有被本轮访问过的位置才会被刷新成当前层的答案。这个进行中混合了新值和旧值的状态是理解倒序遍历的关键。因为一维数组没有行列之分同一块内存里同时躺着两层的信息哪个位置是新值、哪个位置是旧值完全由遍历顺序决定。写成伪代码就是for i in 0..n-1: for j in 从某个方向遍历 0..V: if j w[i]: dp[j] max(dp[j], dp[j - w[i]] v[i])内层那个从某个方向现在必须给出答案。而答案不是想当然的得从dp[j-w[i]]到底代表哪一层这个角度去推。3.3 内层循环的下界不能随意放顺手提一个容易被忽略的细节内层循环其实没必要从V一路跑到w[i]以下再判断。写成for j in range(V, w[i] - 1, -1):直接让下界停在w[i]天然就避开了j w[i]的情况少一层判断代码也更短。这不算什么大优化但在面试手写代码时能少写一行if观感更利落。真正需要注意的是 Python 的range是左闭右开终止值必须写w[i] - 1而不是w[i]这个 off-by-one 我第一次写的时候也栽过结果少更新了一个位置答案生生差了一档。4. 倒序遍历背包容量的真正原因4.1 先看正序会发生什么假设我们把内层改成正序也就是j从w[i]递增到V还是用物品0重量 1价值 15来演示初始dp [0,0,0,0,0]。j 1: dp[1] max(dp[1], dp[0] 15) max(0, 0 15) 15 j 2: dp[2] max(dp[2], dp[1] 15) max(0, 15 15) 30 j 3: dp[3] max(dp[3], dp[2] 15) max(0, 30 15) 45 j 4: dp[4] max(dp[4], dp[3] 15) max(0, 45 15) 60结果dp[4] 60。可整道题只有一件物品它最多只能被拿一次容量 4 的正确答案应该是 15。60 意味着什么意味着物品0被装了四次。也就是说正序循环把 0-1 背包悄悄变成了完全背包。这就是那个改成正序结果还更大看着更优现象的来源。它不是更优它是错的它违反的正是每件物品最多取一次这条最根本的约束。4.2 从读到的是哪个值看倒序现在把j从V递减回w[i]同样的物品0初始dp [0,0,0,0,0]j 4: dp[4] max(dp[4], dp[3] 15) max(0, 0 15) 15 j 3: dp[3] max(dp[3], dp[2] 15) max(0, 0 15) 15 j 2: dp[2] max(dp[2], dp[1] 15) max(0, 0 15) 15 j 1: dp[1] max(dp[1], dp[0] 15) max(0, 0 15) 15结果dp [0, 15, 15, 15, 15]跟二维表的第一行一模一样物品0只被用了一次。差别出在哪就出在dp[j - w[i]]这个被读取的位置上。正序时j - w[i] j而j - w[i]这个位置在本轮循环里已经被更新过了。也就是说读到的dp[j-w[i]]是本轮已经处理过的结果里面已经包含了当前物品 i。拿它去加v[i]等于让物品 i 又被用了一次。一次加一次循环走到底物品 i 就被用了很多次。倒序时j - w[i] j而j - w[i]这个位置在本轮循环里还没轮到它仍然是上一轮前 i-1 件物品留下的旧值。这正好就是状态转移方程里要的dp[i-1][j-w[i]]语义完全吻合。所以那句流传很广的总结其实很精确倒序遍历保证dp[j-w[i]]读到的是上一层的旧值从而保证每件物品只用一次。4.3 一张表看清旧值与新值我做了张对照表这是我认为理解倒序最直观的方式。假设数组内存是物理线性排列的j从 0 到 4本轮要处理物品1重量 3价值 20上一轮结束后的dp是[0, 15, 15, 15, 15]。先看倒序的做法访问顺序当前 j读取 dp[j-w]该位置状态写入 dp[j]第1次4dp[1] 15未处理是旧值35第2次3dp[0] 0未处理是旧值20再看正序的做法把它当成完全背包访问顺序当前 j读取 dp[j-w]该位置状态写入 dp[j]第1次3dp[0] 0旧值暂时没问题20第2次4dp[1] 15旧值也没问题35看到这里你可能会疑惑这个例子里正序和倒序读到的都是旧值啊对因为物品1的重量是 3j - w[i]跳得比较远恰好跳出了本轮会连续更新的区域。这就说明一件事正序的危害不是每次都暴露它只在j - w[i]恰好落在本轮已经更新过的区间里时才显形。物品1之所以没出事是因为dp[1]在本轮没被更新j1 w3根本不进循环。换个物品就露馅了。物品0的重量是 1j - 1永远紧跟在前一个位置正序必然踩雷所以我们才在 4.1 节看到dp[4] 60这种离谱结果。这就是为什么很多人试了一下正序好像也对——他们试的那组数据恰好有重量较大的物品或者 V 比较小误打误撞没触发。这种看起来对是最危险的因为它会让人带着错误认知去写下一题。4.4 别把倒序理解成防止越界有一个流传很广的错误解释说倒序是为了防止j - w[i]出现负数、防止数组越界。这个说法完全站不住脚。防越界靠的是循环下界j w[i]跟正序倒序一点关系都没有——正序从w[i]开始跑同样不会越界。倒序的唯一目的就是保护dp[j-w[i]]这个被依赖位置的旧值不被提前覆盖。这是就地更新时被依赖的位置必须晚于依赖它的位置被更新这条通用规则在背包问题上的具体体现。同一条规则在很多滚动数组的题里都出现过比如最长公共子序列压缩成一维的时候之所以需要额外用一个临时变量保存dp[j-1]的旧值也是同一个道理——只是背包问题里j - w[i] j这个关系恰好和倒序遍历天然契合所以不需要临时变量。提示如果你在别的DP题里看到一维数组需要从后往前更新多半也是同一个原因——避免覆盖掉本次计算还需要的上一层数据。判断方法是看转移方程里依赖的是同层的下标还是上一层的下标。5. 为什么只能先遍历物品不能先遍历背包5.1 阶段和状态的位置不能换前面说过0-1背包的阶段是物品编号 i状态是容量 j。阶段必须放在最外层这不是什么编码习惯而是动态规划递推的结构性要求。原因在于每一轮阶段推进我们都在做一次信息封存处理完第 i 件物品之后dp数组里装的应该是前 i 件物品在所有容量下的最优解第 i 件物品的选/不选这件事就永久定下来了后面不会再翻案。这个整行一次性刷新的过程只能由外层循环承担。如果把容量放外层会发生什么外层每推进一格容量 j内层就把所有物品扫一遍。这时dp数组里装的既不是前 i 件物品的结果也不是前 i-1 件物品的结果它是一堆跨越了所有物品、只处理了部分容量的中间态。你根本没办法把dp[j]对应到任何一张二维表的某一行上语义直接崩了。5.2 用具体数据把先遍历背包的错摆出来空说结构不够我们直接把代码跑出来看结果。两组数据物品0 重量 1 价值 15物品1 重量 2 价值 20容量V 3。正确答案是物品0 物品1重量 3价值 35。先试外层容量从小到大内层物品j 1: 物品0: dp[1] max(0, dp[0]15) 15 物品1: 放不下 j 2: 物品0: dp[2] max(0, dp[1]15) 30 物品1: dp[2] max(30, dp[0]20) 30 j 3: 物品0: dp[3] max(0, dp[2]15) 45 物品1: dp[3] max(45, dp[1]20) 45结果是45比正确答案 35 还大。丢人都丢在明面上物品0 被用了三次111315×345。外层容量递增内层又每次都从头扫物品两个方向的重复使用叠加在一起物品被无限次塞进背包。再试外层容量从大到小内层物品j 3: 物品0: dp[3] max(0, dp[2]15) 15 物品1: dp[3] max(15, dp[1]20) 20 j 2: 物品0: dp[2] max(0, dp[1]15) 15 物品1: dp[2] max(15, dp[0]20) 20 j 1: 物品0: dp[1] max(0, dp[0]15) 15 物品1: 放不下结果是dp[3] 20。这个比正确答案小因为算j 3的时候dp[2]和dp[1]还是初始的 0两个物品根本组合不起来容量 3 最后只塞进去了一件物品1。两个方向一个偏大一个偏小没有一个是能用的。这就是先遍历背包为什么彻底不可行的实证。换个角度再解释一次倒序遍历之所以能救一维数组前提是外层固定了物品 i内层在同一个物品的上下文中横向扫描容量被依赖的位置总是本轮还没碰过的。而一旦外层变成容量这个前提就不存在了——你没法为本轮定义一个统一的物品上下文dp[j-w]里混着哪些物品的贡献完全说不清楚。5.3 什么情况下反过来写反而是对的这里必须补一句否则容易走进另一个极端觉得先遍历容量永远是错的。在一些只问方案数、不问最优值的计数型题目里内外层的顺序决定了你到底在数什么两者都是正确答案只是含义不同。场景外层内层统计含义组合数不区分顺序物品容量从小到大{1,2}和{2,1}算同一种排列数区分顺序容量物品{1,2}和{2,1}算两种0-1 最优值物品容量从大到小每件物品至多一次举个例子用面额 1、2、5 凑出 5 元。如果问有几种组合方式答案是 4 种5111111221112要外层物品、内层容量。如果问有几种排列方式那就是 9 种因为 122、212、221 要算三种得外层容量、内层物品。判断依据很朴素外层循环决定谁是阶段、谁是状态。当阶段在外层时每件物品只会被作为一次独立的决策批次处理天然不区分顺序当容量在外层时容量是阶段每次推进都可以重新挑选任意一件物品顺序信息被保留了下来。所以不能先遍历背包这句话有严格适用范围它针对的是求最优值的一维压缩写法。计数场景下反过来写是另一种题不是错是换了问法。6. 一维写法的完整实现与边界细节6.1 三种语言的实现Python 版本最常见也最简洁def knapsack_01(weights, values, cap): # dp[j] 表示容量上限为 j 时能取到的最大价值 dp [0] * (cap 1) for i in range(len(weights)): w, v weights[i], values[i] # 倒序遍历保证 dp[j - w] 读到的是上一件物品的旧值 for j in range(cap, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[cap]C 版本int knapsack01(const std::vectorint w, const std::vectorint v, int cap) { std::vectorint dp(cap 1, 0); for (size_t i 0; i w.size(); i) { for (int j cap; j w[i]; --j) { dp[j] std::max(dp[j], dp[j - w[i]] v[i]); } } return dp[cap]; }Java 版本int knapsack01(int[] w, int[] v, int cap) { int[] dp new int[cap 1]; for (int i 0; i w.length; i) { for (int j cap; j w[i]; j--) { dp[j] Math.max(dp[j], dp[j - w[i]] v[i]); } } return dp[cap]; }三段代码的结构完全一致把倒序那行改成正序三者就会同步错。所以任何一道题我在写完一维版本之后都会立刻拿一组小数据手动对一遍或者直接跟二维版本对拍不给自己留看着像对的余地。6.2 初始化改一个字语义就换了一道题dp数组的初始值直接决定题目问的是什么不要求装满dp [0] * (cap 1)所有容量都天然可达大不了什么都不装价值 0。恰好装满dp [NEG] * (cap 1); dp[0] 0其中NEG是负无穷。除容量 0 之外的位置都需要靠状态转移凑出来凑不出来的就是负无穷最后如果dp[cap]还是负数说明装不满要按题目要求返回特定值。代码长这样NEG float(-inf) dp [NEG] * (cap 1) dp[0] 0 for i in range(len(weights)): w, v weights[i], values[i] for j in range(cap, w - 1, -1): if dp[j - w] ! NEG: dp[j] max(dp[j], dp[j - w] v)那个if dp[j - w] ! NEG判断不是可选项。如果不加负无穷加上一个正价值有可能变成一个看起来合法的数值在浮点数下-inf x仍然是-inf但如果你用-1之类的整数代替负无穷就会出问题进而污染整个答案。所以我更倾向于用足够小的整数比如-10**9并且在转移时显式判断可达性。6.3 求方案数和求最优值的写法差异顺手把方案数的版本也写出来因为倒序遍历在这类题里同样是刚需def count_ways_01(weights, cap): dp [0] * (cap 1) dp[0] 1 for w in weights: for j in range(cap, w - 1, -1): dp[j] dp[j - w] return dp[cap]这里dp[j] dp[j-w]读的必须是还没把当前物品算进去的方案数否则同一个物品会被重复计入。倒序的理由和求最优值时完全一致。6.4 两个不影响正确性但影响效率的剪枝第一个是内层循环的上界可以收紧。处理第 i 件物品时容量没必要从cap一路扫下来因为前面 i 件物品的总重量是有限的超过这个总和的位置不可能有变化。设sumW为前 i1 件物品的总重量循环上界写成min(cap, sumW)就行。在物品多、容量大的测试用例上这个剪枝能省下可观的时间。第二个是下界的收紧理论上可以算max(w[i], cap - 后面所有物品的重量之和)因为如果连后面所有物品都填不满剩余空间这个位置本轮就不可能有改进。这个优化通常只在物品总重量远小于容量时才有意义一般场景不用折腾。7. 常见问题与排查速查表7.1 出错现象与根因对照这些年被问到的问题里一维背包的错误翻来覆去就那么几类我整理成一张表你在调试时可以直接对号入座现象根因修正方式答案比正确答案大内层容量写成正序物品被重复取退化成了完全背包内层改成从cap递减到w[i]答案比正确答案小且只像装了一件物品外层写成容量物品放到了内层把物品循环提到最外层答案偏小某些容量下明显有更好的组合却没被选中循环下界写错j没跑到w[i]就停了检查range(cap, w[i]-1, -1)的终止值恰好装满的题返回了一个没装满但很大的值初始化全 0没有用负无穷标记不可达dp[0]0其余位置填负无穷方案数算出来是正确答案的若干倍该用组合数写法的地方用了排列数写法组合数要求物品在外层、容量在内层递增二维版本正确、一维版本错误一维压缩时依赖关系被覆盖检查内层方向或退回二维逐行对拍这张表里我觉得最值得反复看的是第一行和第二行。它们是一个硬币的两面倒序遍历解决的是层内覆盖问题物品在外层解决的是阶段划分问题。两个问题独立存在缺一个都不行。我见过有人把倒序改对了但因为物品和容量顺序写反结果还是错的然后以为是倒序没起作用又改回正序越调越乱。7.2 用对拍法验证自己的一维写法最高效的自检方法不是盯着代码看而是写两个函数一个二维版本逻辑直观、几乎不会写错一个一维版本效率高但容易出坑然后造小规模随机数据对拍。import random def brute(weights, values, cap): 暴力搜索作为最终对照 n len(weights) best 0 for mask in range(1 n): tw tv 0 for i in range(n): if mask i 1: tw weights[i] tv values[i] if tw cap: best max(best, tv) return best for _ in range(2000): n random.randint(1, 8) cap random.randint(1, 15) weights [random.randint(1, 8) for _ in range(n)] values [random.randint(1, 20) for _ in range(n)] a knapsack_01(weights, values, cap) b brute(weights, values, cap) assert a b, (weights, values, cap, a, b)跑上两千组如果全部通过基本可以确认一维写法没问题。这个对拍的习惯我从写第一道背包题开始就养成了直到现在还在用因为它能在几十毫秒内把我觉得应该对变成数据说它确实对。尤其是当你在纠结内外层顺序、正序倒序这些细节的时候与其在脑子里模拟循环不如让机器替你试。7.3 我自己踩过的三个坑第一个坑是把dp数组的下标语义搞混。dp[j]里的j是容量上限不是装了多少件。有一次我在方案数版本里把dp[j]当成容量恰好为 j但初始化又写了全 0结果容量 1 到 4 全都返回了 1 种方案因为什么都不装被当成了合法方案。后来我养成一个习惯写初始化之前先用一句话把dp[j]的中文含义念出来念不通就是自己没想清楚。第二个坑是在剪枝的时候把上界写成了cap下界又写了w[i]但物品数组没按重量排序导致j - w[i]在某些轮次里访问到了一个尚未进入有效状态的位置。那题的结论是剪枝一定要在保证语义不变的前提下做任何我觉得这样更快的改动都要回到对拍脚本里验证。第三个坑是语言层面的。Python 的range(cap, w - 1, -1)如果写成range(cap, w, -1)会少遍历一次j w而这个位置往往恰好是只放当前物品的最优解。这个错误在复杂用例上不一定暴露但在cap恰好等于某件物品重量时必错。所以我在写循环边界时尤其是递减的range都会多念一遍右开区间。8. 把这套思路迁移到同类问题上背包问题的这套分析方法其实可以整套搬到别的题上去这是我觉得它最值钱的地方。判断一道题能不能用一维倒序压缩我会问自己三个问题每件物品每个决策单元是不是至多被使用一次如果是内层必须倒序如果可以用无限次内层就得正序这是完全背包如果可以用有限次那就得拆成二进制组或者用单调队列优化。依赖关系指向的是上一层还是同一层指向上一层就是倒序保护旧值指向同一层就是正序利用新值。转移方程里下标是谁答案基本就定了。阶段是哪个维度阶段必须在最外层。物品、天数、区间长度、字符串下标哪个维度承载了不可回退的推进哪个就该放到最外面。拿最长回文子序列、编辑距离这类题套一下也完全对得上它们的阶段是区间长度容量维度被换成了字符串位置一维压缩时同样要考虑覆盖顺序。我甚至写过一个用来检查一维压缩是否合法的小脚本把转移方程里的下标关系解析出来自动提示哪些位置需要倒序——虽然最后没做成什么正经工具但写那个脚本的过程让我彻底记住了这条规则被依赖的位置必须在依赖它的位置之后被更新。回到这道题本身最后再补一句实操层面的建议。如果你正在准备面试或者刷题遇到一维背包卡壳的时候不要在网上反复搜为什么倒序的解释直接打开编辑器把那几行循环改成正序跑一遍把dp数组每一轮的值打印出来和二维版本逐行比。看到dp[4]从 15 变成 60 的那一瞬间你就不需要任何人再给你解释了——那个 60 会替你记住一切。我自己就是这么记下来的比看十篇文章都管用。