动态规划实战：0-1背包问题详解与LeetCode经典题目解析

1. 0-1背包问题入门：从生活场景到算法模型

第一次听说0-1背包问题时，我正坐在咖啡厅里整理旅行装备。面前摊开的行李箱就像是一个背包，而我要决定带哪些物品才能在有限的行李额度内最大化实用价值——这不就是活生生的背包问题吗？

0-1背包问题的核心是：给定一组物品，每个物品有确定的重量和价值，在背包承重限制下，如何选择物品组合使得总价值最大。这里的"0-1"意味着每个物品只能选择拿（1）或不拿（0），不能拆分。

举个具体例子：假设你是个游戏玩家，背包容量4kg，现在有以下装备：

• 长剑：重量3kg，价值1500金币
• 盾牌：重量2kg，价值1200金币
• 药水：重量1kg，价值800金币

暴力解法是列出所有可能的组合（2^3=8种），比如：

1. 只带长剑：1500金币
2. 长剑+药水：2300金币（最优解）
3. 盾牌+药水：2000金币 ...

当物品数量达到20个时，组合数就超过百万——这就是为什么我们需要动态规划（DP）来优化。DP通过存储中间计算结果，将指数级复杂度降为多项式级。

2. 二维DP解法：庖丁解牛

2.1 DP数组的构建逻辑

我第一次理解二维DP解法时，画了整整三页纸的表格。关键是要明白dp[i][j]表示：考虑前i个物品，在背包容量j时的最大价值。

继续用之前的例子，我们构建如下DP表：

2.2 递推公式的实战理解

递推公式dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])包含两个关键选择：

1. 不选当前物品：直接继承上一行的结果（dp[i-1][j]）
2. 选择当前物品：用剩余空间的最大价值加上当前物品价值

以dp[2][3]（考虑盾牌，容量3kg）为例：

• 不选盾牌：沿用dp[1][3] = 800
• 选盾牌：dp[1][1] + 1200 = 800 + 1200 = 2000取较大值2000。

2.3 完整Java实现

public int knapsack2D(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n+1][capacity+1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (j < weights[i-1]) { dp[i][j] = dp[i-1][j]; } else { dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] ); } } } return dp[n][capacity]; }

注意：实际代码中物品索引从0开始，而DP表行号从1开始，所以有weights[i-1]的偏移

3. 一维DP优化：空间压缩的艺术

3.1 为什么能降维？

观察二维DP表会发现，每一行其实只依赖上一行。这意味着我们可以只用一维数组，通过反向遍历来避免覆盖需要的数据。

3.2 关键实现细节

public int knapsack1D(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity+1]; for (int i = 0; i < weights.length; i++) { for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]); } } return dp[capacity]; }

为什么必须反向遍历？假设我们正序遍历：

• 计算dp[2]时可能已经使用了当前物品
• 计算dp[4]时又可能重复使用该物品 这就变成了完全背包问题（物品可重复取）。

3.3 调试技巧

在初学阶段，我习惯在每次外层循环后打印DP数组：

System.out.println("处理物品"+i+"后：" + Arrays.toString(dp));

这会输出类似：

处理物品0后：[0, 800, 800, 800, 800] 处理物品1后：[0, 800, 1200, 2000, 2000] 处理物品2后：[0, 800, 1200, 1500, 2300]

4. LeetCode实战：识别背包问题变种

4.1 416. 分割等和子集

这道题可以转化为：能否找到一些数，其和等于总和的一半。相当于：

• 背包容量：sum/2
• 物品重量=物品价值=数组元素
• 求是否能恰好装满背包

public boolean canPartition(int[] nums) { int sum = Arrays.stream(nums).sum(); if (sum % 2 != 0) 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]; }

4.2 1049. 最后一块石头的重量 II

这道题的精妙之处在于：将石头分成两堆，使两堆重量差最小。转化思路：

1. 计算总重量sum
2. 求不超过sum/2的最大子集和（背包问题）
3. 结果就是sum - 2*最大子集和

public int lastStoneWeightII(int[] stones) { int sum = Arrays.stream(stones).sum(); int target = sum / 2; int[] dp = new int[target + 1]; for (int stone : stones) { for (int j = target; j >= stone; j--) { dp[j] = Math.max(dp[j], dp[j - stone] + stone); } } return sum - 2 * dp[target]; }

4.3 494. 目标和

这道题需要转换思路为：找到和为(target + sum)/2的子集数目。递推公式变为计数型：

public int findTargetSumWays(int[] nums, int target) { int sum = Arrays.stream(nums).sum(); if ((sum + target) % 2 != 0 || sum < Math.abs(target)) return 0; int bagSize = (sum + target) / 2; int[] dp = new int[bagSize + 1]; dp[0] = 1; for (int num : nums) { for (int j = bagSize; j >= num; j--) { dp[j] += dp[j - num]; } } return dp[bagSize]; }

5. 常见误区与调试技巧

在刷题过程中，我踩过不少坑，这里分享几个典型问题：

1. 初始化错误：忘记初始化dp[0]=1（计数问题）或dp[0]=0（价值问题）
2. 遍历顺序错误：该倒序时用了正序，导致物品重复计算
3. 边界条件：没有处理sum为奇数的情况（416题）
4. 空间估算不足：当target很大时，DP数组可能超出内存限制

调试时建议：

• 先用手动计算小测试案例
• 打印中间DP表状态
• 对于边界情况（如空数组、单个元素）单独测试

记住DP问题的解决流程：

1. 识别问题是否属于背包类型
2. 确定背包容量和物品属性
3. 选择DP数组维度
4. 确定递推公式
5. 处理初始化和遍历顺序
6. 考虑空间优化可能