登录
用填充表格法吃透01背包及其变形-3
三、01背包的经典变形
01背包的核心是「选/不选」，实际考题中很少直接考查基础模型，更多是结合具体场景转化为变形问题。但无论场景如何变化，只要抓住「每个物品最多选一次」的本质，就能用DP解题5步「万能钥匙」轻松破解。以下是4类最经典的01背包变形：
3.1 变形1：目标和（分割子集和/是否能装满背包）
LeetCode 链接：494. 目标和
问题描述：给定一个非负整数数组nums和一个目标数target，向数组中每个整数前添加+或-，使得所有整数的和等于target，求有多少种不同的添加符号的方法。
核心转化：设添加+的数的和为left，添加-的数的和为right，则有：
left - right = target
left + right = sum(nums)
两式相加得：left = (target + sum(nums)) / 2
问题转化为：从nums中选择若干元素，使得其和恰好为left，求这样的选择方案数——这是「01背包求方案数」的典型场景（每个元素选或不选，选则计入和，不选则不计）。
目标和问题核心表格（空表，后续逐步填充）：
| 处理阶段\和为j | 0 | 1 | 2 | ...（和递增） | left（目标和） |
|---|---|---|---|---|---|
| 初始状态 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第1个元素 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第2个元素 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
表格说明：表格中每个单元格dp[i][j]代表「处理前i个元素后，能凑出和为j的方案数」，最终右下角dp[n][left]即为目标和的解法总数（n为nums数组长度）。
3.1.1 步骤1：确定dp数组及下标的含义
定义二维数组dp[i][j]：表示「处理前i个元素，能凑出和为j的方案数」。后续可优化为一维数组dp[j]（空间优化思路与基础01背包一致），这里先从直观的二维数组入手。
对应表格维度：i（行）表示处理的元素个数（从0到n，0代表未处理任何元素），j（列）表示要凑的和（从0到left，0代表和为0），表格共n+1行、left+1列。
3.1.2 步骤2：确定递推公式
对于第i个元素（值为nums[i-1]，数组索引从0开始，i从1开始），核心决策仍是「选或不选」，方案数为两种决策的总和：
-
不选第i个元素：凑出和为j的方案数 = 处理前i-1个元素凑出和为j的方案数，即
dp[i][j] += dp[i-1][j]； -
选第i个元素：需保证j ≥ nums[i-1]（当前元素值不大于目标和j），此时方案数 = 处理前i-1个元素凑出和为j-nums[i-1]的方案数，即
dp[i][j] += dp[i-1][j - nums[i-1]]。
最终递推公式（两种决策方案数相加）：
if (j >= nums[i - 1]) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
3.1.3 步骤3：dp数组如何初始化
初始化核心是确定边界条件，即无需推导就能直接确定的方案数：
-
i=0（未处理任何元素），j=0（和为0）：不选任何元素即可凑出和为0，因此方案数为1，即
dp[0][0] = 1； -
i=0（未处理任何元素），j>0（和大于0）：没有元素可选，无法凑出任何正和，方案数为0，即
dp[0][j] = 0（j>0）； -
j=0（和为0），i>0（处理过元素）：初始时可先设为1（后续通过递推更新），表示不选当前及之前元素的基础方案。
结合示例理解：假设nums = [1,1,1,1]，target = 2，先计算sum(nums) = 4，left = (2 + 4)/2 = 3。初始化后的表格（第0行已填充）：
| 处理阶段\和为j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 初始状态（i=0） | 1 | 0 | 0 | 0 |
| 处理第1个元素（1） | 1 | 待填 | 待填 | 待填 |
| 处理第2个元素（1） | 1 | 待填 | 待填 | 待填 |
| 处理第3个元素（1） | 1 | 待填 | 待填 | 待填 |
| 处理第4个元素（1） | 1 | 待填 | 待填 | 待填 |
3.1.4 步骤4：确定遍历顺序（表格填充顺序）
与基础01背包二维解法一致：先遍历元素（i从1到n），再遍历和（j从0到left），即逐行填充表格。原因：计算dp[i][j]时，仅依赖上一行（i-1行）的dp[i-1][j]和dp[i-1][j - nums[i-1]]，逐行填充可确保依赖的单元格已提前计算完成。
3.1.5 步骤5：打印dp数组（验证）
以示例nums = [1,1,1,1]、target = 2（left=3）为例，逐步填充表格验证逻辑：
-
填充第1行（i=1，元素1：1）：
- j=0：不选元素1，方案数=dp[0][0]=1；
- j=1：j≥1，方案数=dp[0][1]（不选）+ dp[0][0]（选）=0+1=1；
- j=2：j>1，无法选，方案数=dp[0][2]=0；
- j=3：j>1，无法选，方案数=dp[0][3]=0；
-
填充第2行（i=2，元素2：1）：
- j=0：方案数=dp[1][0]=1；
- j=1：j≥1，方案数=dp[1][1]（不选）+ dp[1][0]（选）=1+1=2；
- j=2：j≥1，方案数=dp[1][2]（不选）+ dp[1][1]（选）=0+1=1；
- j=3：j>1，无法选，方案数=dp[1][3]=0；
-
填充第3行（i=3，元素3：1）：
- j=0：方案数=dp[2][0]=1；
- j=1：j≥1，方案数=dp[2][1]（不选）+ dp[2][0]（选）=2+1=3；
- j=2：j≥1，方案数=dp[2][2]（不选）+ dp[2][1]（选）=1+2=3；
- j=3：j≥1，方案数=dp[2][3]（不选）+ dp[2][2]（选）=0+1=1；
-
填充第4行（i=4，元素4：1）：
- j=0：方案数=dp[3][0]=1；
- j=1：j≥1，方案数=dp[3][1]（不选）+ dp[3][0]（选）=3+1=4；
- j=2：j≥1，方案数=dp[3][2]（不选）+ dp[3][1]（选）=3+3=6；
- j=3：j≥1，方案数=dp[3][3]（不选）+ dp[3][2]（选）=1+3=4；
最终填充完成的表格：
| 处理阶段\和为j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 初始状态（i=0） | 1 | 0 | 0 | 0 |
| 处理第1个元素（1） | 1 | 1 | 0 | 0 |
| 处理第2个元素（1） | 1 | 2 | 1 | 0 |
| 处理第3个元素（1） | 1 | 3 | 3 | 1 |
| 处理第4个元素（1） | 1 | 4 | 6 | 4 |
表格右下角dp[4][3] = 4，即该示例的目标和解法总数为4，与实际情况一致（+1+1+1-1、+1+1-1+1、+1-1+1+1、-1+1+1+1）。
3.1.6 目标和问题完整代码（二维+一维优化）
/**
* 目标和（二维DP解法）
* @param {number[]} nums - 非负整数数组
* @param {number} target - 目标和
* @returns {number} - 不同的添加符号方法数
*/
function findTargetSumWays_2d(nums, target) {
const sum = nums.reduce((a, b) => a + b, 0);
// 边界条件：target的绝对值大于sum，或(target + sum)为奇数，均无可行方案
if (Math.abs(target) > sum || (target + sum) % 2 !== 0) return 0;
const left = (target + sum) / 2;
const n = nums.length;
// 初始化二维dp数组：dp[i][j]表示处理前i个元素凑出和为j的方案数
const dp = new Array(n + 1).fill(0).map(() => new Array(left + 1).fill(0));
dp[0][0] = 1; // 未处理元素时，凑出和为0的方案数为1
// 遍历顺序：先遍历元素，再遍历和（逐行填充）
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= left; j++) {
// 递推公式
if (j >= nums[i - 1]) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 打印dp数组验证
console.log('目标和二维DP数组（表格）：');
for (let i = 0; i <= n; i++) {
console.log(dp[i].join('\t'));
}
return dp[n][left];
}
/**
* 目标和（一维DP空间优化解法）
* @param {number[]} nums - 非负整数数组
* @param {number} target - 目标和
* @returns {number} - 不同的添加符号方法数
*/
function findTargetSumWays_1d(nums, target) {
const sum = nums.reduce((a, b) => a + b, 0);
if (Math.abs(target) > sum || (target + sum) % 2 !== 0) return 0;
const left = (target + sum) / 2;
// 初始化一维dp数组：dp[j]表示凑出和为j的方案数
const dp = new Array(left + 1).fill(0);
dp[0] = 1; // 基础方案：不选任何元素凑出和为0
// 遍历顺序：先遍历元素，再倒序遍历和（避免重复选择）
for (let num of nums) {
for (let j = left; j >= num; j--) {
dp[j] += dp[j - num]; // 递推公式简化（复用数组）
}
console.log(`处理完元素${num}后，dp数组：`, [...dp]);
}
return dp[left];
}
// 测试用例
const nums = [1, 1, 1, 1];
const target = 2;
console.log('二维DP解法：', findTargetSumWays_2d(nums, target)); // 输出：4
console.log('一维DP解法：', findTargetSumWays_1d(nums, target)); // 输出：4
3.2 变形2：分割等和子集（是否能装满背包）
LeetCode 链接：416. 分割等和子集
问题描述：给定一个只包含正整数的非空数组nums，判断是否可以将这个数组分割成两个子集，使得两个子集的和相等。
核心转化：两个子集和相等，即每个子集的和为数组总和的一半（记为target）。问题转化为：从nums中选择若干元素，使得其和恰好为target——这是「01背包判断可行性」的典型场景（每个元素选或不选，判断是否能装满容量为target的背包）。
核心表格（空表）：
| 处理阶段\和为j | 0 | 1 | 2 | ...（和递增） | target（目标和） |
|---|---|---|---|---|---|
| 初始状态 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第1个元素 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第2个元素 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
表格说明：表格中每个单元格dp[i][j]代表「处理前i个元素后，能否凑出和为j」（布尔值），最终右下角dp[n][target]即为问题答案。
3.2.1 步骤1：确定dp数组及下标的含义
定义二维布尔数组dp[i][j]：表示「处理前i个元素，能否凑出和为j」。可优化为一维布尔数组dp[j]，空间复杂度从O(n*target)降至O(target)。
对应表格维度：i（行）表示处理的元素个数（从0到n，0代表未处理任何元素），j（列）表示要凑的和（从0到target，0代表和为0），表格共n+1行、target+1列。
3.2.2 步骤2：确定递推公式
对于第i个元素（值为nums[i-1]），决策为「选或不选」，可行性为两种决策的或运算：
-
不选第i个元素：能否凑出j = 处理前i-1个元素能否凑出j，即
dp[i][j] = dp[i-1][j]； -
选第i个元素：需j ≥ nums[i-1]，能否凑出j = 处理前i-1个元素能否凑出j-nums[i-1]，即
dp[i][j] = dp[i-1][j - nums[i-1]]。
最终递推公式（两种决策有一个可行则整体可行）：
if (j >= nums[i - 1]) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
3.2.3 步骤3：dp数组如何初始化
初始化核心是确定边界条件，即无需推导就能直接确定的可行性：
-
i=0（未处理任何元素），j=0（和为0）：不选任何元素可凑出和为0，因此
dp[0][0] = true； -
i=0（未处理任何元素），j>0（和大于0）：没有元素可选，无法凑出任何正和，可行性为
false，即dp[0][j] = false（j>0）； -
j=0（和为0），i>0（处理过元素）：初始时可先设为
true（后续通过递推更新），表示不选当前及之前元素的基础方案。
结合示例理解：假设nums = [1,5,11,5]，sum = 22，target = 11。初始化后的表格（第0行已填充）：
| 处理阶段\和为j | 0 | 1 | 2 | 3 | ...（和递增） | 11（目标和） |
|---|---|---|---|---|---|---|
| 初始状态（i=0） | true | false | false | false | false | false |
| 处理第1个元素（1） | true | 待填 | 待填 | 待填 | 待填 | 待填 |
| 处理第2个元素（5） | true | 待填 | 待填 | 待填 | 待填 | 待填 |
| 处理第3个元素（11） | true | 待填 | 待填 | 待填 | 待填 | 待填 |
| 处理第4个元素（5） | true | 待填 | 待填 | 待填 | 待填 | 待填 |
3.2.4 步骤4：确定遍历顺序（表格填充顺序）
与基础01背包二维解法一致：先遍历元素（i从1到n），再遍历和（j从0到target），即逐行填充表格。原因：计算dp[i][j]时，仅依赖上一行（i-1行）的dp[i-1][j]和dp[i-1][j - nums[i-1]]，逐行填充可确保依赖的单元格已提前计算完成。
一维解法：先遍历元素，再倒序遍历和（避免重复选择），与基础01背包空间优化逻辑一致。
3.2.5 步骤5：打印dp数组（验证）
以示例nums = [1,5,11,5]、sum = 22、target = 11为例，逐步填充表格验证逻辑：
-
填充第1行（i=1，元素1：1）：
- j=0：不选元素1，dp[1][0] = dp[0][0] = true；
- j=1：j≥1，dp[1][1] = dp[0][1]（不选）|| dp[0][0]（选）= false || true = true；
- j=2-11：j<1，无法选，dp[1][j] = dp[0][j] = false；
-
填充第2行（i=2，元素2：5）：
- j=0：dp[2][0] = dp[1][0] = true；
- j=1-4：j<5，无法选，dp[2][j] = dp[1][j]（继承上一行）；
- j=5：j≥5，dp[2][5] = dp[1][5]（不选）|| dp[1][0]（选）= false || true = true；
- j=6：j≥5，dp[2][6] = dp[1][6]（不选）|| dp[1][1]（选）= false || true = true；
- j=7-11：j≥5，dp[2][j] = dp[1][j]（不选）|| dp[1][j-5]（选），其中j=11时，dp[2][11] = false || false = false；
-
填充第3行（i=3，元素3：11）：
- j=0-10：j<11，无法选，dp[3][j] = dp[2][j]（继承上一行）；
- j=11：j≥11，dp[3][11] = dp[2][11]（不选）|| dp[2][0]（选）= false || true = true；
-
填充第4行（i=4，元素4：5）：
- j=0-4：j<5，无法选，dp[4][j] = dp[3][j]（继承上一行）；
- j=5-11：j≥5，dp[4][j] = dp[3][j]（不选）|| dp[3][j-5]（选），其中j=11时，dp[4][11] = true || false = true；
最终填充完成的表格：
| 处理阶段\和为j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始状态（i=0） | true | false | false | false | false | false | false | false | false | false | false | false |
| 处理第1个元素（1） | true | true | false | false | false | false | false | false | false | false | false | false |
| 处理第2个元素（5） | true | true | false | false | false | true | true | false | false | false | false | false |
| 处理第3个元素（11） | true | true | false | false | false | true | true | false | false | false | false | true |
| 处理第4个元素（5） | true | true | false | false | false | true | true | false | false | false | false | true |
表格右下角dp[4][11] = true，即该示例可以分割成两个和相等的子集（子集[1,5,5]和[11]），与预期结果一致。
3.2.6 分割等和子集完整代码
/**
* 分割等和子集（二维DP解法）
* @param {number[]} nums - 正整数数组
* @returns {boolean} - 是否可以分割成两个和相等的子集
*/
function canPartition_2d(nums) {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false; // 总和为奇数，无法分割
const target = sum / 2;
const n = nums.length;
// 初始化二维dp数组：dp[i][j]表示处理前i个元素能否凑出和为j
const dp = new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(false));
dp[0][0] = true; // 边界条件
// 遍历顺序：先遍历元素，再遍历和
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= target; j++) {
if (j >= nums[i - 1]) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 打印dp数组验证
console.log('分割等和子集二维DP数组（表格）：');
for (let i = 0; i <= n; i++) {
console.log(dp[i].map(val => (val ? 'true' : 'false')).join('\t'));
}
return dp[n][target];
}
/**
* 分割等和子集（一维DP空间优化解法）
* @param {number[]} nums - 正整数数组
* @returns {boolean} - 是否可以分割成两个和相等的子集
*/
function canPartition_1d(nums) {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
const target = sum / 2;
// 初始化一维dp数组：dp[j]表示能否凑出和为j
const dp = new Array(target + 1).fill(false);
dp[0] = true; // 边界条件
// 遍历顺序：先遍历元素，再倒序遍历和
for (let num of nums) {
for (let j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
console.log(
`处理完元素${num}后，dp数组：`,
dp.map(val => (val ? 'true' : 'false'))
);
}
return dp[target];
}
// 测试用例
const nums1 = [1, 5, 11, 5];
console.log('二维DP解法：', canPartition_2d(nums1)); // 输出：true
console.log('一维DP解法：', canPartition_1d(nums1)); // 输出：true
const nums2 = [1, 2, 3, 5];
console.log('二维DP解法：', canPartition_2d(nums2)); // 输出：false
console.log('一维DP解法：', canPartition_1d(nums2)); // 输出：false
3.3 变形3：最后一块石头的重量II（最小背包剩余容量）
LeetCode 链接：1049. 最后一块石头的重量 II
问题描述：有一堆石头，每块石头的重量都是正整数。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为x和y，且x ≤ y。那么粉碎的可能结果如下：如果x == y，那么两块石头都会被完全粉碎；如果x != y，那么重量为x的石头会被完全粉碎，而重量为y的石头会变成y - x的重量。最后，最多只会剩下一块石头。返回此石头的最小可能重量。
核心转化：要使最后剩余石头重量最小，需将石头尽可能分成两堆重量接近的石头——两堆重量差越小，剩余重量越小。设总重量为sum，目标是找到一堆石头的最大重量maxWeight（≤ sum/2），则剩余重量为sum - 2*maxWeight。问题转化为：从石头重量数组中选择若干元素，使得其和不超过sum/2的最大值——这是「01背包求最大价值（重量即价值）」的场景（背包容量为sum/2，物品重量和价值均为石头重量）。
最后一块石头的重量II核心表格（空表，后续逐步填充）：
| 处理阶段\容量j | 0 | 1 | 2 | ...（容量递增） | target（sum/2） |
|---|---|---|---|---|---|
| 初始状态 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第1块石头 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 处理第2块石头 | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
表格说明：表格中每个单元格dp[j]代表「容量为j的背包能容纳的最大重量」（一维DP），最终dp[target]即为不超过sum/2的最大子集重量，剩余重量 = sum - 2*dp[target]。
3.3.1 步骤1：确定dp数组及下标的含义
定义一维数组dp[j]：表示「容量为j的背包，能容纳的最大重量」（即选若干石头的最大和）。
对应表格维度：仅保留"容量j"这一列维度（j从0到target，target = sum/2向下取整），形成单行表格，每次遍历石头时，滚动更新这一行的数值（覆盖上一行的结果）。
3.3.2 步骤2：确定递推公式
对于第i块石头（重量stones[i]，价值也为stones[i]），有两种核心决策：选或不选。
-
不选第i块石头：容量为j的最大重量 = 不选当前石头时的最大重量，即
dp[j] = dp[j]（保持不变）； -
选第i块石头：需保证背包容量j ≥ 第i块石头的重量，此时最大重量 = 容量j-stones[i]的最大重量 + 第i块石头的重量，即
dp[j] = dp[j - stones[i]] + stones[i]。
最终递推公式（取两种决策的最大值）：
if (j >= stones[i]) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
} else {
dp[j] = dp[j]; // 容量不足，无法选
}
简化后（因为容量不足时dp[j]不变）：
for (let j = target; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
3.3.3 步骤3：dp数组如何初始化
初始化逻辑与基础01背包一维DP一致：容量为0时，最大重量为0，因此dp[0] = 0；其他容量的初始值也为0（因为初始无石头可放，最大重量为0），即dp = new Array(target + 1).fill(0)。
初始化后的单行表格：[0,0,0,0,...]（j从0到target）
结合示例理解：假设stones = [2,7,4,1,8,1]，sum = 23，target = Math.floor(23/2) = 11。初始化后的表格：
| 容量j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3.3.4 步骤4：确定遍历顺序（表格填充顺序）
一维DP的遍历顺序有严格要求，核心是「倒序遍历容量」，对应单行表格的「从右往左填充」：
-
必须先遍历石头，再遍历容量：逐个处理每块石头，每次处理时更新整个单行表格（覆盖上一行结果）；
-
容量必须倒序遍历（j从target到stones[i]）：从最大容量往小容量填充，确保计算
dp[j]时，dp[j - stones[i]]仍是上一行（未处理当前石头）的旧值，避免同一石头被多次选择。
3.3.5 步骤5：打印dp数组（验证）
通过打印单行表格的滚动更新过程，验证填充规则的正确性。仍用测试用例 stones = [2,7,4,1,8,1]、sum = 23、target = 11，演示一维DP数组（单行表格）的填充变化：
-
初始状态：dp = [0,0,0,0,0,0,0,0,0,0,0,0]
-
处理石头1（w=2），j从11到2倒序：更新后：dp = [0,0,2,2,2,2,2,2,2,2,2,2]
- j=11：dp[11] = max(0, dp[9]+2) = max(0,0+2)=2；
- j=10：dp[10] = max(0, dp[8]+2)=2；
- ...（j=2到9同理）；
- j=2：dp[2] = max(0, dp[0]+2)=2；
-
处理石头2（w=7），j从11到7倒序：更新后：dp = [0,0,2,2,2,2,2,7,7,9,9,9]
- j=11：max(2, dp[4]+7)=max(2,2+7)=9；
- j=10：max(2, dp[3]+7)=max(2,2+7)=9；
- j=9：max(2, dp[2]+7)=max(2,2+7)=9；
- j=8：max(2, dp[1]+7)=max(2,0+7)=7；
- j=7：max(2, dp[0]+7)=max(2,0+7)=7；
-
处理石头3（w=4），j从11到4倒序：更新后：dp = [0,0,2,2,4,4,6,7,7,9,9,11]
- j=11：max(9, dp[7]+4)=max(9,7+4)=11；
- j=10：max(9, dp[6]+4)=max(9,2+4)=9；
- j=9：max(9, dp[5]+4)=max(9,2+4)=9；
- j=8：max(7, dp[4]+4)=max(7,2+4)=7；
- j=7：max(7, dp[3]+4)=max(7,2+4)=7；
- j=6：max(2, dp[2]+4)=max(2,2+4)=6；
- j=5：max(2, dp[1]+4)=max(2,0+4)=4；
- j=4：max(2, dp[0]+4)=max(2,0+4)=4；
-
处理石头4（w=1），j从11到1倒序：更新后：dp = [0,1,2,3,4,5,6,7,8,9,10,11]
- j=11：max(11, dp[10]+1)=max(11,9+1)=11；
- j=10：max(9, dp[9]+1)=max(9,9+1)=10；
- ...（其他位置类似更新）；
-
处理石头5（w=8），j从11到8倒序：更新后：dp = [0,1,2,3,4,5,6,7,8,9,10,11]
- j=11：max(11, dp[3]+8)=max(11,3+8)=11；
- j=10：max(10, dp[2]+8)=max(10,2+8)=10；
- j=9：max(9, dp[1]+8)=max(9,1+8)=9；
- j=8：max(8, dp[0]+8)=max(8,0+8)=8；
-
处理石头6（w=1），j从11到1倒序：最终：dp = [0,1,2,3,4,5,6,7,8,9,10,11]
最终单行表格dp[11] = 11，剩余重量 = 23 - 2*11 = 1，与预期结果一致。
3.3.6 最后一块石头的重量II完整代码（一维DP）
/**
* 最后一块石头的重量II（一维DP解法）
* @param {number[]} stones - 石头重量数组
* @returns {number} - 最后剩余石头的最小可能重量
*/
function lastStoneWeightII(stones) {
const sum = stones.reduce((a, b) => a + b, 0);
const target = Math.floor(sum / 2);
// 初始化一维dp数组：dp[j]表示容量为j的背包能容纳的最大重量
const dp = new Array(target + 1).fill(0);
// 遍历顺序：先遍历石头，再倒序遍历容量
for (let stone of stones) {
for (let j = target; j >= stone; j--) {
dp[j] = Math.max(dp[j], dp[j - stone] + stone);
}
console.log(`处理完石头${stone}后，dp数组：`, [...dp]);
}
// 剩余重量 = 总重量 - 2*最大子集重量
return sum - 2 * dp[target];
}
// 测试用例
const stones = [2, 7, 4, 1, 8, 1];
console.log('最后剩余石头的最小重量：', lastStoneWeightII(stones)); // 输出：1
3.4 变形4：一和零（二维背包容量）
LeetCode 链接：474. 一和零
问题描述：给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。
核心转化：每个字符串是一个"物品"，选择该物品会消耗"0的数量"和"1的数量"两种容量，目标是在两种容量均不超过限制（m、n）的前提下，选择最多的物品——这是「二维容量01背包求最大物品数」的场景（背包有两个维度的容量限制，价值为1，求最大价值即最大物品数）。
一和零问题核心表格（空表，后续逐步填充）：
| 0的数量\1的数量j | 0 | 1 | 2 | ...（1的数量递增） | n（最大1的数量） |
|---|---|---|---|---|---|
| 0（0的数量为0） | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| 1（0的数量为1） | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| ...（0的数量递增） | 待填充 | 待填充 | 待填充 | 待填充 | 待填充 |
| m（最大0的数量） | 待填充 | 待填充 | 待填充 | 待填充 | 待填充（最终答案：最多字符串数量） |
表格说明：表格中每个单元格dp[i][j]代表「最多使用i个0和j个1时，能选择的最大字符串数量」，我们的目标是按规则填充表格，最终右下角dp[m][n]即为一和零问题的答案。
3.4.1 步骤1：确定dp数组及下标的含义
定义二维数组dp[i][j]：表示「最多用i个0和j个1能选择的最大字符串数量」。
对应表格维度：i（行）表示0的数量（从0到m，0代表0个0），j（列）表示1的数量（从0到n，0代表0个1），表格共m+1行、n+1列。
3.4.2 步骤2：确定递推公式
对于每个字符串（含zero个0、one个1），有两种核心决策：选或不选。
-
不选当前字符串：最多用i个0和j个1的最大字符串数量 = 不选当前字符串时的最大数量，即
dp[i][j] = dp[i][j]（保持不变）； -
选当前字符串：需保证i ≥ zero且j ≥ one（0和1的数量都足够），此时最大数量 = 用i-zero个0和j-one个1的最大数量 + 1（当前字符串），即
dp[i][j] = dp[i - zero][j - one] + 1。
最终递推公式（取两种决策的最大值）：
if (i >= zero && j >= one) {
dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
} else {
dp[i][j] = dp[i][j]; // 容量不足，无法选
}
简化后（因为容量不足时dp[i][j]不变，且使用倒序遍历）：
for (let i = m; i >= zero; i--) {
for (let j = n; j >= one; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
}
}
3.4.3 步骤3：dp数组如何初始化
初始化逻辑：初始无字符串可选，无论有多少0和1，最大字符串数量都为0，因此dp[i][j] = 0（所有单元格初始化为0），即dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))。
初始化后的表格（所有单元格为0）：
| 0的数量\1的数量j | 0 | 1 | 2 | ... | n |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| ... | 0 | 0 | 0 | 0 | 0 |
| m | 0 | 0 | 0 | 0 | 0 |
结合示例理解：假设strs = ["10","0001","111001","1","0"]，m = 5，n = 3。初始化后的表格（5+1行，3+1列）：
| 0的数量\1的数量j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 |
3.4.4 步骤4：确定遍历顺序（表格填充顺序）
二维容量01背包的遍历顺序有严格要求：
-
必须先遍历字符串（物品），再遍历0的数量，最后遍历1的数量：逐个处理每个字符串，每次处理时更新整个二维表格；
-
0和1的数量都必须倒序遍历：
- 0的数量倒序遍历（i从m到zero）：确保计算
dp[i][j]时，dp[i - zero][j - one]仍是上一轮（未处理当前字符串）的旧值； - 1的数量倒序遍历（j从n到one）：同样确保依赖的单元格是旧值。
- 0的数量倒序遍历（i从m到zero）：确保计算
倒序遍历避免同一字符串被多次选择，完美契合01背包「每个物品选一次」的规则。
3.4.5 步骤5：打印dp数组（验证）
以示例strs = ["10","0001","111001","1","0"]、m = 5、n = 3为例，逐步填充表格验证逻辑：
-
处理字符串1（"10"：zero=1, one=1）：
- 更新dp[1][1]到dp[5][3]范围内所有满足i≥1且j≥1的位置
- dp[1][1] = max(0, dp[0][0]+1) = max(0,0+1) = 1
- dp[2][2] = max(0, dp[1][1]+1) = max(0,1+1) = 2
- ...（其他位置类似）
-
处理字符串2（"0001"：zero=3, one=1）：
- 更新dp[3][1]到dp[5][3]范围内所有满足i≥3且j≥1的位置
- dp[3][1] = max(dp[3][1], dp[0][0]+1) = max(0,0+1) = 1
- dp[4][2] = max(dp[4][2], dp[1][1]+1) = max(0,1+1) = 2
- ...（其他位置类似）
-
处理字符串3（"111001"：zero=2, one=4）：
- 由于one=4 > n=3，无法选择此字符串，dp数组不变
-
处理字符串4（"1"：zero=0, one=1）：
- 更新dp[0][1]到dp[5][3]范围内所有满足j≥1的位置
- dp[0][1] = max(0, dp[0][0]+1) = max(0,0+1) = 1
- dp[1][2] = max(dp[1][2], dp[1][1]+1) = max(0,1+1) = 2
- ...（其他位置类似）
-
处理字符串5（"0"：zero=1, one=0）：
- 更新dp[1][0]到dp[5][3]范围内所有满足i≥1的位置
- dp[1][0] = max(0, dp[0][0]+1) = max(0,0+1) = 1
- dp[2][1] = max(dp[2][1], dp[1][1]+1) = max(0,1+1) = 2
- ...（其他位置类似）
最终填充完成的表格（简化展示关键部分）：
| 0的数量\1的数量j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 2 | 2 | 2 |
| 2 | 1 | 2 | 3 | 3 |
| 3 | 1 | 2 | 3 | 3 |
| 4 | 1 | 2 | 3 | 4 |
| 5 | 1 | 2 | 3 | 4 |
表格右下角dp[5][3] = 4，即该示例的最大子集长度为4，与预期结果一致。
3.4.6 一和零完整代码（二维DP）
/**
* 一和零（二维DP解法）
* @param {string[]} strs - 二进制字符串数组
* @param {number} m - 最多允许的0的数量
* @param {number} n - 最多允许的1的数量
* @returns {number} - 最大子集长度
*/
function findMaxForm(strs, m, n) {
// 初始化二维dp数组：dp[i][j]表示i个0和j个1能选的最大字符串数
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// 遍历每个字符串（物品）
for (let str of strs) {
// 统计当前字符串的0和1的数量
let zero = 0,
one = 0;
for (let c of str) {
c === '0' ? zero++ : one++;
}
// 倒序遍历0的数量，再倒序遍历1的数量（避免重复选择）
for (let i = m; i >= zero; i--) {
for (let j = n; j >= one; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
}
}
// 打印每次处理后的dp数组（简化打印，只打印部分关键行）
console.log(`处理完字符串"${str}"后，dp数组（前5行前5列）：`);
for (let i = 0; i <= Math.min(m, 5); i++) {
console.log(dp[i].slice(0, Math.min(n, 5)).join('\t'));
}
}
return dp[m][n];
}
// 测试用例
const strs = ['10', '0001', '111001', '1', '0'];
const m = 5,
n = 3;
console.log('最大子集长度：', findMaxForm(strs, m, n)); // 输出：4
四、01背包问题总结
01背包的核心是「选或不选」的二选一决策，所有变形都围绕这一核心逻辑，通过转化「物品」「容量」「目标」的含义，适配不同的实际场景。掌握以下关键点，可轻松破解所有01背包相关问题：
-
表格可视化核心：DP解题的本质是填充表格，先明确表格形态（dp数组含义），再按规则填充，表格填完即得答案；
-
5步万能钥匙：确定dp含义→递推公式→初始化→遍历顺序→验证，这是所有DP问题的通用拆解思路，尤其适用于背包问题；
-
空间优化技巧：二维DP可通过「倒序遍历容量」优化为一维DP，核心是复用数组空间，避免重复选择物品；
-
变形转化逻辑：无论场景如何变化，只要每个物品最多选一次，都可转化为01背包模型——关键是找到「物品」（待选择的元素/字符串等）、「容量」（限制条件，如重量、和、0/1数量等）、「目标」（最大价值、可行性、方案数等）。
通过基础模型+变形练习，熟练掌握表格填充逻辑和5步拆解方法，就能将复杂的DP问题转化为有序的表格填充过程，彻底攻克01背包这一DP核心模型。
