动态规划实战：背包问题与经典题型解析

1. 动态规划专题精讲：从背包问题到经典题型实战

今天想和大家分享我在算法训练中遇到的三个典型动态规划问题：1049. 最后一块石头的重量 II、494. 目标和、474.一和零。这三个题目看似不同，实则都蕴含着动态规划的核心思想，特别适合用来训练我们拆解问题的能力。我会从问题本质出发，带大家一步步推导状态转移方程，并分享我在解题过程中积累的实用技巧。

2. 1049. 最后一块石头的重量 II：背包问题的变形

2.1 问题重述与本质分析

题目描述：有一堆石头，每块石头的重量都是正整数。每次任意选两块石头碰撞，较重石头重量减去较轻石头重量，最终求可能的最小剩余重量。

这道题看似是模拟碰撞过程，实则可以转化为经典的背包问题。关键在于理解：将石头分成两组，使两组重量差最小。这本质上等价于在总重量为sum的石头中，选取一部分石头，使其重量尽可能接近sum/2。

2.2 动态规划解法详解

1. 计算所有石头的总重量sum
2. 目标转化为求容量为sum//2的背包能装下的最大重量
3. 定义dp数组：dp[j]表示容量为j的背包能装下的最大重量
4. 状态转移方程： dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
5. 最终结果为sum - 2*dp[sum//2]

关键技巧：这里使用一维dp数组优化空间复杂度，遍历顺序需要从后往前，避免重复计算。

2.3 代码实现与优化

def lastStoneWeightII(stones): total = sum(stones) target = total // 2 dp = [0] * (target + 1) for stone in stones: for j in range(target, stone - 1, -1): dp[j] = max(dp[j], dp[j - stone] + stone) return total - 2 * dp[target]

时间复杂度：O(n×sum)，其中n为石头数量 空间复杂度：O(sum)

3. 494. 目标和：01背包的计数问题

3.1 问题转化思路

题目要求：给定非负整数数组和一个目标数S，通过在数字前添加+或-，使表达式结果为S，求共有多少种方法。

这个问题可以转化为：找到子集，使得正数子集和减去负数子集和等于S。设正数子集和为x，则有： x - (sum - x) = S => 2x = sum + S => x = (sum + S)/2

因此问题转化为：在数组中选取若干数，使其和为(sum+S)/2，求方案数。

3.2 动态规划解法

1. 计算数组总和sum
2. 检查(sum + S)是否为偶数且非负
3. 定义dp[j]：装满容量为j的背包有dp[j]种方法
4. 初始化：dp[0] = 1（和为0有一种方法：不选任何数）
5. 状态转移方程： dp[j] += dp[j - nums[i]]

3.3 完整代码实现

def findTargetSumWays(nums, S): total = sum(nums) if (total + S) % 2 != 0 or total < abs(S): return 0 target = (total + S) // 2 dp = [0] * (target + 1) dp[0] = 1 for num in nums: for j in range(target, num - 1, -1): dp[j] += dp[j - num] return dp[target]

常见错误：忘记检查(sum + S)的奇偶性，导致出现小数目标值；没有处理S可能为负数的情况。

4. 474. 一和零：二维背包问题

4.1 问题特点分析

题目要求：在字符串数组中找到最大的子集，使得子集中0的数量不超过m，1的数量不超过n。

这是典型的二维背包问题，需要同时考虑两个维度的限制（0的数量和1的数量）。

4.2 动态规划解法设计

1. 定义dp[i][j]：最多有i个0和j个1的最大子集大小
2. 初始化：dp[0][0] = 0
3. 对于每个字符串，统计其中0和1的数量zeros和ones
4. 状态转移方程： dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)

4.3 代码实现与优化

def findMaxForm(strs, m, n): dp = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: zeros = s.count('0') ones = len(s) - zeros for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1) return dp[m][n]

时间复杂度：O(l×m×n)，其中l为字符串数量 空间复杂度：O(m×n)

5. 动态规划解题通用技巧

5.1 问题识别特征

1. 求最值问题（最大/最小）
2. 能否将问题分解为子问题
3. 子问题之间是否存在重叠

5.2 解题四步法

1. 确定dp数组及下标的含义
2. 确定递推公式（状态转移方程）
3. dp数组如何初始化
4. 确定遍历顺序

5.3 常见错误与调试技巧

1. 数组越界：检查dp数组大小是否足够
2. 初始化错误：特别是dp[0]的初始化
3. 遍历顺序错误：01背包问题必须从后往前遍历
4. 状态转移方程错误：多打印中间结果验证

6. 三种背包问题对比

7. 算法优化实战心得

1. 空间优化：一维dp数组可以大幅减少空间复杂度，但要注意遍历顺序
2. 剪枝技巧：在目标和问题中，提前判断(sum+S)的奇偶性可以避免无效计算
3. 预处理：在一和零问题中，预先统计每个字符串的0和1数量可以提高效率
4. 调试方法：打印dp表格是验证算法正确性的有效手段，特别是在二维dp问题中

在实际刷题过程中，我发现动态规划问题的难点往往不在于编码，而在于如何将原问题转化为标准的dp模型。这需要大量的练习和经验积累。建议从简单的背包问题开始，逐步过渡到更复杂的变种。