刷动态规划刷到第 35 天终于撞上了背包问题。背包问题在动态规划里的地位差不多相当于排序在数组里的地位绕不开而且吃透它对后面理解状态定义和空间优化帮助很大。今天这篇就围绕两个主题一个是 0-1 背包问题的二维 DP 完整写法也就是标题里说的“背包问题二维”另一个是 LeetCode 第 416 题分割等和子集它本质上是背包问题的变体也可以直接套二维 DP 甚至一维滚动数组解决。适合正在刷题准备面试、或者刚学到动态规划想找一条完整学习链路的人参考。先聊一个最直接的感受背包问题第一次接触时会觉得状态特别多物品、重量、价值、容量四个东西搅在一起。但只要把它落到一张二维表上问题会立刻清晰起来。416 题就是检验你是否真懂这张表的好题目——它不是求最大价值而是问能不能恰好凑出一个目标值语义从“最大值”换成了“存在性”其他逻辑几乎原封不动。提示下面所有代码都假设每件物品只能选一次也就是严格的 0-1 背包语义。1. 为什么 0-1 背包要开二维数组先看一次贪心的失败1.1 贪心方案错在哪很多人第一次看到 0-1 背包脑子里蹦出来的是性价比排序先按价值/重量从大到小排然后能塞就塞。我当年也是这么写的直到被一个很简单的反例打脸。假设背包容量是 11三件物品的重量和价值分别是物品重量价值性价比A710约 1.43B68约 1.33C561.2按性价比贪心先拿 A剩余容量 4B 和 C 都放不下最终总价值 10。但真正的答案是拿 B 和 C重量 6 5 11 正好装满总价值 8 6 14。A 虽然单件性价比高但它块头太大把本可以组成更优组合的空间占死了。这个反例说明一个核心问题0-1 背包的每一件物品都是不可分割的选择 A 相当于放弃了用 B C 去填满背包的可能而贪心只看局部的单位价值看不到全局的组合效用。分数背包可以按性价比拿因为能把物品切到刚好装满0-1 背包不行。所以你需要的不是每一步都选当前最优而是把每一种组合都考虑一遍后再选全局最优。动态规划干的就是这件事二维数组则是承载所有组合情况的天然容器。1.2 二维状态到底在表达什么0-1 背包问题常用状态定义是dp[i][j] 在前 i 件物品中做选择总重量不超过 j 时能获得的最大价值。第一维 i 是“决策边界”到底考虑了前几件物品第二维 j 是“容量边界”背包还剩多少空间或者说当前枚举的容量上限。这两个维度一旦定义清楚下面所有公式都是顺理成章的。我觉得用购物券类比例子很好理解你手里有一套面额不同的购物券每件商品只能买一次现在想知道在预算不超过 j 的前提下从前 i 件商品里能挑出的最高总价值。dp[i][j] 就是答案。对每一件商品要么不买保持上一行同预算的结果要么买先把预算减掉它的价格再看上一行在剩余预算下的最优。两种选择取更大值就是这一格的结果。需要特别强调“不超过 j”和“恰好等于 j”的差别。这组题的很多变体都是在这两个语义之间切换的。标准 0-1 背包求的是不超过容量时的最大价值所以 dp 初始化为 0 是安全的416 题求的是能否恰好凑出 target初始化和判断逻辑都会跟着变化这个区别后面会专门讲。二维数组在这里不是一个实现细节而是把原问题拆成子问题的物理化表达。每一行代表引入一件新物品后所有可能预算下的全局最优。后面的所有优化都是在这个表的基础上做减法。2. 构建二维 DP 表转移方程、填表顺序与初始化2.1 状态转移方程怎么来从 dp[i][j] 的定义出发对第 i 件物品重量 w[i]价值 v[i]只有两条路不取它问题退化为在前 i - 1 件物品里选重量不超过 j也就是 dp[i - 1][j]。取它前提是 j 必须大于等于 w[i]那么剩余容量 j - w[i] 在前 i - 1 件物品里继续选最优再加上当前价值即 dp[i - 1][j - w[i]] v[i]。取两边的最大值dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i])这里有个非常容易踩的坑第二项为什么写 dp[i - 1][j - w[i]]而不是 dp[i][j - w[i]]区别在于前者是从还没考虑第 i 件物品的旧状态转移过来保证第 i 件物品只被选这一次后者在同一轮里可能已经包含了第 i 件物品于是它能被反复使用这就成了完全背包的递推式。0-1 背包和完全背包表面上只差这一个下标语义却完全不同。2.2 用一张表走一遍只看公式可能觉得抽象我拿一组小数据手动填一遍重量 w [1, 3, 4]价值 v [15, 20, 30]背包容量 C 4。初始化 dp[0][j] 全为 0表示没有物品可选时任何容量下的价值都是 0。依次处理三件物品得到如下表格ij0j1j2j3j40无物品000001w1, v150151515152w3, v200151520353w4, v30015152035重点看第 2 行第 4 列。当处理到第 2 件物品重量 3、价值 20时j 4不取它沿用上一行 dp[1][4] 15取它需要回到 dp[1][4 - 3] dp[1][1] 15再加 20得到 35。两个选择取 max所以是 35。这就是重量 1 的物品和重量 3 的物品都被选中的结果。再看第 3 行当第 3 件物品进入候选后j 4 时取它只有 dp[2][0] 30 30不如上一行的 35于是保持 35。最终 dp[3][4] 35这就是正确答案选重量 1 和重量 3 的物品总重量正好 4价值 35。手动填这张表比盯着公式看十遍更有效。我建议初学者至少完整填一次体会每一格都是在上一行结果和上一行某个偏左位置加当前价值之间取大。2.3 初始化和遍历顺序初始化没有太多玄机dp[0][j] 0dp[i][0] 0。前者没有物品后者容量为 0两个都不能漏。外层循环按物品 i 从 1 到 n内层循环按容量 j 从 0 到 C。为什么外层必须是物品而不是容量因为表格的每一行都依赖上一行逐行计算时上一行已经完整存在直接查表即可同一行内部其实没有依赖j 从小到大还是从大到小在二维版里都不影响结果习惯上从小到大即可。这一阶段的目标是把二维版彻底写熟练。我见过很多同学一上来就背一维优化结果遇到要求输出具体方案的题就懵。二维表其实是所有背包变体问题的母版后面的完全背包、多重背包、分组背包追根溯源都是在这个转移思想上改条件。3. 416 题怎么变成背包分割等和子集的转化过程3.1 从“两堆相等”到“凑半和”LeetCode 416 题描述很简单给定一个只包含正整数的非空数组问能不能把它分成两个子集使得两个子集的元素和相等。直接枚举子集组合复杂度是 2 的 n 次方肯定不现实。常规思路是先把问题转化一下设数组总和为 sum如果两个子集和相等那么每个子集的和必须是 sum / 2所以 sum 为奇数时直接返回 false。接下来问题就变成能不能从原数组中选出一部分数使它们的和恰好等于 target sum / 2。这一步转化本质上是把分割成两个集合等价成找到一个子集恰好凑出半和因为剩下的数自然就是另一个子集。很多题解都默认这个等价关系成立但刚开始刷题时值得自己推一遍如果存在一个子集和等于 target那么剩余元素的和就是 sum - target target两个子集和相等原题成立反过来如果能分成两个和相等的子集那任意一个子集的和就是 target。双向都成立转化无懈可击。3.2 布尔 dp 的状态定义与转移416 题和标准 0-1 背包的区别在于它不求最大值只问存在性。所以 dp 数组类型从 int 变成 boolean语义变成dp[i][j] 在前 i 个数中能否选出若干个数使它们的和恰好等于 j。转移也非常自然不选当前数 nums[i - 1]结果继承 dp[i - 1][j]选当前数前提是 j 大于等于 nums[i - 1]结果看 dp[i - 1][j - nums[i - 1]]两种情况只要有一种为 truedp[i][j] 就是 true。于是dp[i][j] dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]初始化时需要 dp[0][0] true前 0 个数凑出 0是一个都不选当然成立。其他位置默认 false。有一个常见误区是把所有 dp[i][j] 都记为 true觉得反正能选一部分数所以要宽松一点结果递推时几乎每个位置都会被标记成 true整个 dp 表报废。正确理解是dp[0][0] 是唯一能凭空成立的源头其他 true 必须由它一步步推导出来。3.3 Java 实现与边界判断先放二维版本的 Java 代码class Solution { public boolean canPartition(int[] nums) { int sum 0; for (int num : nums) { sum num; } if ((sum 1) 1) { return false; } int target sum / 2; int n nums.length; boolean[][] dp new boolean[n 1][target 1]; dp[0][0] true; for (int i 1; i n; i) { int w nums[i - 1]; for (int j 0; j target; j) { if (j w) { dp[i][j] dp[i - 1][j]; } else { dp[i][j] dp[i - 1][j] || dp[i - 1][j - w]; } } } return dp[n][target]; } }这里有个小优化在求 target 之后可以先检查数组里是否存在某个数大于 target。因为所有数都是正整数一旦某个数比 target 还大它既不能被放进半和子集也可以直接断定 false。这个判断和 dp 计算互不影响能省掉不少无效循环。比如 nums [1, 5, 11, 5]sum 22target 11。手动推一遍可以选 1、5、5 得到 11所以返回 true。再比如 nums [1, 2, 3, 5]sum 11 是奇数直接返回 false不需要进 dp。这两个例子也是我在本地最常用的冒烟测试。4. 一维滚动优化为什么必须倒着更新容量4.1 二维空间浪费在哪里二维布尔数组的大小是 (n 1) 乘 (target 1)。当 n 到几百、target 到几千时这个矩阵可能就有几十万上百万个布尔值空间上勉强能接受但面试里后一步几乎一定会问你能不能把第一维省掉观察转移方程可以发现dp[i][j] 只依赖 dp[i - 1][j] 和 dp[i - 1][j - w]也就是只依赖上一行。既然如此没必要保留全部历史行只需要一行数组边遍历边覆盖。这就是滚动数组的思路。一维数组的状态含义要跟着调整dp[j] 处理到当前物品时能否凑出总和恰好为 j。每处理一个物品就尝试更新一遍 dp[j]更新完后 dp[j] 代表的是包含当前物品候选之后的结果。4.2 正序更新的错误一维优化的关键在容量循环的方向。正确的写法是容量从 target 倒着往下走到不小于当前数的位置为止for (int num : nums) { for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } }为什么一定要倒序因为 dp[j] 和 dp[j - num] 在同一行数组里如果正序更新较小的 j 可能已经被当前这个物品更新过了等更新到较大的 j 时dp[j - num] 里已经包含了当前物品被使用过的信息相当于同一个物品被用了两次。举个极端的反例nums [1]target 2。如果正序遍历j 1dp[1] | dp[0]变成 truej 2dp[2] | dp[1]而 dp[1] 这时已经是 true于是 dp[2] 变成 true。但数组里根本没有两个 1怎么可能凑出 2这就是重复使用当前物品的典型错误。改成倒序j 2dp[2] | dp[1]此刻 dp[1] 还是 false还没被更新dp[2] 保持 falsej 1dp[1] | dp[0]变成 true。结果就对了。这个例子虽然小却是理解一维背包最关键的钥匙。理解这一点之后完全背包问题的正序更新也就迎刃而解——完全背包本来就允许同一件物品用多次所以它用正序。4.3 一维代码与二维保留的取舍416 题的一维版本非常简洁class Solution { public boolean canPartition(int[] nums) { int sum 0; for (int num : nums) { sum num; } if ((sum 1) 1) { return false; } int target sum / 2; boolean[] dp new boolean[target 1]; dp[0] true; for (int num : nums) { for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; } }这里初始化只需要 dp[0] true不需要其它位置为 true原因和二维一样一切可凑出的和都必须从空集凑出 0 出发。转移时 j 从 target 开始到 num 结束凡是 j num 的位置都不可能选当前数自然也不用更新。二维版本适合讲清思路一维版本适合写进提交。我的建议是不要直接背一维先亲手写过一遍完整的二维表明白每个格子是怎么来的再谈压缩。面试时也建议先铺垫二维的状态定义和转移方程再展示如何优化成一维这比分分钟背出一段代码要有说服力得多。5. 刷题过程中的常错点与校验方法5.1 三个高频翻车点结合我周边同事和自己在刷题群看到的提问416 题和 0-1 背包最常见的错误基本集中在三个地方。第一个是把布尔 dp 初始化为全 true。有人觉得“前 i 个数总能凑出 0所以 dp[i][0] 应该都是 true”这句话本身没错但如果在初始化时把整行都设置成 true那就等于把所有容量直接判死。正确做法是只让 dp[0][0] 为 truedp[i][0] 在递推过程中会自动沿 dp[i - 1][0] 传递下来。第二个是一维数组容量正序更新导致同一物品被重复选取。前面已经用 nums [1]、target 2 的例子演示过现象上是本来 false 的 dp[target] 变成了 true而且只有在某些数据规模下才会暴露非常隐蔽。第三个是忘记判断 sum 的奇偶性或 target 为 0 的情况。416 题数组元素是正整数sum 为奇数必为 false。target 为 0 只有当 sum 为 0 时才会出现题目的正整数约束已经排除掉了但如果你把模板改用到别的场景需要额外带上这个边界。5.2 用暴力枚举校验 dp 结果小数据量的时候我会写一个简单的回溯枚举器来对照 dp 答案快速定位是 dp 的问题还是数据理解的问题boolean bruteCanPartition(int[] nums, int target) { return dfs(nums, 0, target); } boolean dfs(int[] nums, int idx, int remain) { if (remain 0) { return true; } if (idx nums.length || remain 0) { return false; } return dfs(nums, idx 1, remain) || dfs(nums, idx 1, remain - nums[idx]); }这个暴力解法在 n 大于 25 左右就会开始卡顿但它用来验证小样例足够可靠。把 dp 结果和暴力结果对拍是确认边界处理是否正确的习惯性做法不只是这一题适用。5.3 我常用的自测用例我本地跑 416 题会固定放这么几个用例输入期望结果覆盖点[1, 5, 11, 5]true官方经典用例[1, 2, 3, 5]falsesum 为奇数[1, 2, 5]falsesum 为偶数但凑不出 target[1, 2, 2, 3]true多个组合可凑出 target[1]false单个元素不可分割对于 0-1 背包最大价值版本我常用 w [1, 3, 4]、v [15, 20, 30]、C 4 的 35 来验证以及 C 11、w [7, 6, 5]、v [10, 8, 6] 的 14 来验证贪心反例场景。5.4 二维和一维的选择经验最后分享一点实际经验面试手写背包问题时不要一上来就写一维。先写二维把定义、转移、初始化讲清楚让面试官确认你没有理解偏差然后再提出可以用滚动数组把空间压到 O(target)现场演示倒序更新。这个节奏通常比直接丢一维版本更稳也更容易避免因为少写一个边界条件导致的隐性 bug。另一个长期收益的建议把 0-1 背包、完全背包、416 题放在一起对比学习。三者核心差异只在容量循环方向和一维 dp 的更新语义上。背包问题二维表是这一切的地基416 则是验证这个地基是否牢固的试金石。我自己刷完这三类题后再遇到“能否凑出某个和为 k 的子集”“最多能装多少价值且恰好装满”这类变体时基本都能一眼看出该套哪套框架这大概就是 Day 35 真正值回票价的地方。