动态规划背包问题精讲与LeetCode实战

1. 动态规划背包问题精讲

动态规划是算法面试中的常客，而背包问题更是动态规划中的经典题型。最近在刷LeetCode时，我集中攻克了几道背包问题的变种题目，发现这类问题虽然变化多端，但核心思想却高度一致。今天我就来分享一下416、1049、494、474这四道题的解题思路，希望能帮助大家更好地掌握背包问题的解题技巧。

2. 背包问题基础回顾

2.1 背包问题基本概念

背包问题通常描述为：给定一组物品，每个物品有自己的重量和价值，在限定的背包容量下，如何选择物品使得背包中的总价值最大。最基本的背包问题分为：

• 0-1背包：每个物品只能选或不选
• 完全背包：每个物品可以选多次
• 多重背包：每个物品有数量限制

2.2 动态规划解法框架

背包问题的标准解法是动态规划，其核心在于状态转移方程。对于0-1背包问题，我们通常使用二维DP数组：

• dp[i][j]表示前i个物品，背包容量为j时的最大价值
• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

在实际编码中，我们通常会优化为一维数组，通过逆序遍历来节省空间。

3. 分割等和子集问题(416)

3.1 问题分析

题目要求判断一个数组能否被分割成两个子集，使得两个子集的和相等。这实际上可以转化为背包问题：

• 背包容量为数组总和的一半
• 每个物品的重量和价值都是其数值
• 我们需要判断是否能恰好装满这个背包

3.2 解题代码解析

class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (auto a : nums) { sum += a; } if (sum % 2 != 0) // 总和为奇数直接返回false return false; sum /= 2; vector<int> dp(sum + 1); // dp[j]表示容量为j的背包能装的最大价值 for (int i = 0; i < nums.size(); i++) { for (int j = sum; j >= nums[i]; j--) { // 逆序遍历避免重复计算 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } } return dp[sum] == sum; // 判断是否能恰好装满 } };

3.3 关键点说明

1. 总和检查：如果总和为奇数，直接返回false，因为无法平分
2. 背包容量：设置为sum/2，即我们需要找到一个子集的和等于总和的一半
3. 逆序遍历：这是0-1背包的标准优化技巧，确保每个物品只被使用一次
4. 状态转移：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])，这里价值和重量都是nums[i]

注意：在实际面试中，可以先用数学方法快速判断总和是否为奇数，这是一个很好的优化点。

4. 最后一块石头的重量II(1049)

4.1 问题转化

这道题看似与背包无关，但经过分析可以发现：

• 将石头分成两堆，使两堆的重量差最小
• 这相当于找一个子集，使其和尽可能接近总和的一半
• 因此可以转化为背包容量为sum/2的背包问题

4.2 解题代码解析

class Solution { public: int lastStoneWeightII(vector<int>& stones) { int total = 0; for (auto a : stones) { total += a; } int sum = total / 2; vector<int> dp(sum + 1); for (int i = 0; i < stones.size(); i++) { for (int j = sum; j >= stones[i]; j--) { dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); } } return total - 2 * dp[sum]; // 计算两堆的差值 } };

4.3 解题思路详解

1. 计算总和：首先计算所有石头的总重量
2. 背包容量：设置为总重量的一半，这样能最小化两堆的差值
3. 动态规划：使用标准的0-1背包解法，找到不超过sum的最大子集和
4. 结果计算：最终结果为(total - dp[sum]) - dp[sum] = total - 2*dp[sum]

技巧：这道题的关键在于将"最小化两堆差值"转化为"最大化一堆且不超过sum/2"的背包问题。

5. 目标和问题(494)

5.1 问题分析

这道题要求通过加减号组合使表达式结果等于目标值。我们可以将其转化为：

• 设加号数字和为pos，减号数字和为neg
• pos - neg = target
• pos + neg = sum
• 解得：pos = (target + sum)/2
• 因此问题转化为：找出和为(target+sum)/2的子集个数

5.2 解题代码解析

class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum = 0; for (int i = 0; i < nums.size(); i++) sum += nums[i]; if (abs(target) > sum) // 目标值超过总和，不可能 return 0; if ((target + sum) % 2 == 1) // 不是整数，不可能 return 0; int bagSize = (target + sum) / 2; vector<int> dp(bagSize + 1, 0); dp[0] = 1; // 初始条件：和为0有一种方法（不选任何数） for (int i = 0; i < nums.size(); i++) { for (int j = bagSize; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; // 组合数累加 } } return dp[bagSize]; } };

5.3 关键点说明

1. 数学转化：将加减问题转化为子集和问题
2. 边界检查：target绝对值大于sum直接返回0
3. 奇偶检查：如果(target+sum)是奇数，无法平分，返回0
4. 动态规划：这里dp[j]表示和为j的组合数，状态转移是累加而非取max

注意事项：这道题的dp数组初始条件很关键，dp[0]=1表示和为0有一种方法（空集）。

6. 一和零问题(474)

6.1 问题分析

这道题是二维背包问题：

• 每个字符串有0和1两种"重量"
• 背包有两个容量限制：m个0和n个1
• 需要找到最多数量的字符串，使其0和1的总数不超过限制

6.2 解题代码解析

class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (string str : strs) { int oneNum = 0, zeroNum = 0; for (char c : str) { // 统计当前字符串的0和1数量 if (c == '0') zeroNum++; else oneNum++; } // 二维背包的双重逆序遍历 for (int i = m; i >= zeroNum; i--) { for (int j = n; j >= oneNum; j--) { dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; } };

6.3 解题思路详解

1. 统计01数量：对每个字符串，统计其中0和1的个数
2. 二维动态规划：dp[i][j]表示i个0和j个1限制下的最大字符串数量
3. 状态转移：对于每个字符串，逆序更新dp数组
4. 结果返回：dp[m][n]就是最终结果

技巧：虽然是二维背包，但核心思想与一维背包相同，只是需要双重循环来更新状态。

7. 背包问题总结与心得

7.1 解题通用步骤

通过这几道题的练习，我总结出背包问题的通用解题步骤：

1. 识别问题类型：判断是否属于背包问题及其变种
2. 确定背包容量：明确什么是"重量"，什么是"价值"
3. 初始化DP数组：根据问题要求设置初始状态
4. 实现状态转移：根据问题类型编写正确的状态转移方程
5. 返回最终结果：确定DP数组的哪个位置是最终答案

7.2 常见错误与调试技巧

在实际编码中，我遇到过几个常见错误：

1. 遍历顺序错误：0-1背包必须逆序遍历，完全背包则正序遍历
2. 初始条件错误：如494题中dp[0]必须初始化为1
3. 维度理解错误：如474题需要理解二维背包的概念
4. 边界条件遗漏：如416题需要先检查总和是否为奇数

调试时可以：

1. 打印DP表格：观察状态转移是否符合预期
2. 从小例子开始：先用简单测试案例验证
3. 逐步验证：检查每一步的逻辑是否正确

7.3 性能优化建议

对于背包问题的性能优化：

1. 空间优化：尽量使用一维DP数组
2. 提前终止：如416题发现总和为奇数可直接返回
3. 剪枝策略：根据问题特点添加提前终止条件
4. 输入预处理：如474题可以预先统计所有字符串的01数量

经过这组题目的练习，我对背包问题的理解更加深入了。特别是如何将看似不相关的问题转化为背包问题，这种思维转换能力在算法面试中非常重要。建议大家在刷题时多思考问题的本质，而不仅仅是记忆解法。