动态规划实战：背包问题的三种经典变体解析

1. 动态规划实战背包问题的三种经典变体动态规划是算法学习中的核心内容而背包问题又是动态规划中最具代表性的题型。今天我将分享三种背包问题的变体解法这些题目都来自力扣中等难度题库但实际考察频率很高。我会从问题分析、状态转移推导到代码实现带你完整走一遍解题思路。2. 最后一块石头的重量 II2.1 问题重述与转化题目描述有一堆石头用整数数组 stones 表示其中 stones[i] 表示第 i 块石头的重量。每次可以任意选两块石头进行粉碎假设石头重量分别为 x 和 y粉碎后可能得到三种结果x y两块石头完全粉碎x y剩下重量为 x - y 的石头x y剩下重量为 y - x 的石头最终最多只会剩下一块石头返回此石头最小的可能重量。这道题看似是模拟题实际上可以转化为经典的背包问题。关键在于理解题目本质我们需要将石头分成两堆使两堆的重量差最小。这就是典型的分割等和子集问题的变种。2.2 动态规划解法详解2.2.1 状态定义定义 dp[i] 表示背包容量为 i 时能装下的最大石头重量。我们的目标是找到一个容量为 sum/2 的背包能装下的最大重量其中 sum 是所有石头的总重量。2.2.2 状态转移方程对于每块石头我们有两种选择不放入背包dp[j] 保持不变放入背包dp[j] max(dp[j], stones[i] dp[j - stones[i]])注意这里需要从后向前遍历避免重复计算这是01背包问题的经典处理方式。2.2.3 完整代码实现public int lastStoneWeightII(int[] stones) { int sum IntStream.of(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], stone dp[j - stone]); } } return sum - 2 * dp[target]; }2.3 复杂度分析与优化时间复杂度O(n * target)其中 n 是石头数量target 是 sum/2 空间复杂度O(target)注意在实际面试中可以提到如果 sum 很大时可以考虑使用位运算优化或者剪枝策略。3. 目标和问题3.1 问题描述与数学转化给定一个非负整数数组 nums 和一个整数 target向数组中的每个整数前添加 或 -然后串联起来构成一个表达式返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。这道题的关键在于数学转化设正数和为 left负数和绝对值为 right有 left - right target又因为 left right sum数组总和联立可得 left (sum target) / 2这样问题就转化为在数组中找出若干数使其和为 (sum target)/2 的组合数。3.2 动态规划解法3.2.1 状态定义定义 dp[i][j] 表示使用前 i 个物品装满容量为 j 的背包的方法数。3.2.2 状态转移方程对于每个数字 nums[i]我们有两种选择不选dp[i][j] dp[i-1][j]选dp[i][j] dp[i-1][j - nums[i]]初始化时需要注意dp[0][0] 1空集也是一种方案处理 nums[i] 0 的特殊情况3.2.3 完整代码实现public int findTargetSumWays(int[] nums, int target) { int sum IntStream.of(nums).sum(); if ((sum target) % 2 ! 0 || sum Math.abs(target)) { return 0; } int bag (target sum) / 2; int[] dp new int[bag 1]; dp[0] 1; for (int num : nums) { for (int j bag; j num; j--) { dp[j] dp[j - num]; } } return dp[bag]; }3.3 注意事项边界条件检查(sum target) 必须是偶数且 sum ≥ |target|空间优化使用一维数组代替二维数组处理0的特殊情况0可以选或不选不影响和4. 一和零问题4.1 问题描述给你一个二进制字符串数组 strs 和两个整数 m 和 n请你找出并返回 strs 的最大子集的大小该子集中最多有 m 个 0 和 n 个 1。这是典型的多维背包问题每个字符串都有两个维度的重量0的个数和1的个数我们需要在不超过容量限制的情况下选择最多的物品。4.2 动态规划解法4.2.1 状态定义定义 dp[i][j] 表示使用 i 个 0 和 j 个 1 能组成的最大子集大小。4.2.2 状态转移方程对于每个字符串统计其0的个数 zeros 和1的个数 ones dp[i][j] max(dp[i][j], dp[i-zeros][j-ones] 1)同样需要从后向前遍历避免重复计算。4.2.3 完整代码实现public int findMaxForm(String[] strs, int m, int n) { int[][] dp new int[m 1][n 1]; for (String str : strs) { int zeros 0, ones 0; for (char c : str.toCharArray()) { if (c 0) zeros; else ones; } for (int i m; i zeros; i--) { for (int j n; j ones; j--) { dp[i][j] Math.max(dp[i][j], dp[i - zeros][j - ones] 1); } } } return dp[m][n]; }4.3 优化与扩展预处理可以预先计算每个字符串的0和1的个数避免重复计算空间优化虽然已经是二维但可以进一步考虑滚动数组扩展类似思路可以解决更多维度的背包问题5. 动态规划解题心得在实际解决动态规划问题时我总结了以下几个关键步骤问题转化很多看似不是背包问题的问题经过适当转化后可以套用背包模型。比如最后一块石头转化为分割子集问题。状态定义明确 dp 数组的含义这是解题的基础。常见的有一维/二维背包有时需要增加维度。转移方程考虑选与不选两种情况这是动态规划的核心思想。初始化特别是边界条件的处理比如 dp[0] 的取值。遍历顺序01背包通常需要倒序遍历完全背包则是正序。空间优化在面试中从二维优化到一维往往能加分。在实现时我建议先写出基础版的二维DP确保逻辑正确再考虑空间优化特别注意边界条件和特殊输入如空数组、全0等情况动态规划需要大量练习才能掌握建议从背包问题入手逐步扩展到其他类型的DP问题。这三个题目都是很好的练习素材建议反复琢磨其中的状态转移过程。