刷动态规划刷到第 35 天，终于撞上了背包问题。背包问题在动态规划里的地位，差不多相当于排序在数组里的地位，绕不开，而且吃透它对后面理解状态定义和空间优化帮助很大。今天这篇就围绕两个主题：一个是 0-1 背包问题的二维 DP 完整写法，也就是标题里说的“背包问题二维”；另一个是 LeetCode 第 416 题分割等和子集，它本质上是背包问题的变体，也可以直接套二维 DP 甚至一维滚动数组解决。适合正在刷题准备面试、或者刚学到动态规划想找一条完整学习链路的人参考。

先聊一个最直接的感受：背包问题第一次接触时会觉得状态特别多，物品、重量、价值、容量四个东西搅在一起。但只要把它落到一张二维表上，问题会立刻清晰起来。416 题就是检验你是否真懂这张表的好题目——它不是求最大价值，而是问能不能恰好凑出一个目标值，语义从“最大值”换成了“存在性”，其他逻辑几乎原封不动。

提示：下面所有代码都假设每件物品只能选一次，也就是严格的 0-1 背包语义。

1. 为什么 0-1 背包要开二维数组：先看一次贪心的失败

1.1 贪心方案错在哪

很多人第一次看到 0-1 背包，脑子里蹦出来的是性价比排序：先按价值/重量从大到小排，然后能塞就塞。我当年也是这么写的，直到被一个很简单的反例打脸。

假设背包容量是 11，三件物品的重量和价值分别是：

按性价比贪心，先拿 A，剩余容量 4，B 和 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。依次处理三件物品，得到如下表格：

重点看第 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] = 0，dp[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]]；
• 两种情况只要有一种为 true，dp[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 = 22，target = 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 = 1：dp[1] |= dp[0]，变成 true；
• j = 2：dp[2] |= dp[1]，而 dp[1] 这时已经是 true，于是 dp[2] 变成 true。

但数组里根本没有两个 1，怎么可能凑出 2？这就是重复使用当前物品的典型错误。改成倒序：

• j = 2：dp[2] |= dp[1]，此刻 dp[1] 还是 false（还没被更新），dp[2] 保持 false；
• j = 1：dp[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] 为 true，dp[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 题会固定放这么几个用例：

对于 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 真正值回票价的地方。