《LeetCode 1049 最后一块石头的重量||》

一、题目1049. 最后一块石头的重量 II - 力扣LeetCode二、做题思路问题转化前置分析每次粉碎两块石头本质上是将石头分成两堆然后不断抵消最终剩下的重量等于两堆重量之差的绝对值。设所有石头总重量为sum两堆重量分别为a和b则a b sum最终剩余重量为|a - b|。为了使剩余重量最小应使两堆重量尽可能接近即让其中一堆的重量不超过sum/2且尽可能大。因此问题转化为从数组中选取若干块石头使其总重量不超过sum/2求该总重量能取到的最大值即 01 背包容量为sum/2的最大价值问题。1. 状态表示核心基础定义dp[i][j]表示从前i块石头中选取若干块总重量不超过j时能获得的最大总重量。i范围0到nj范围0到targettarget sum/2。该状态与标准 01 背包完全一致价值就是重量本身。2. 状态转移方程关键难点对于第i块石头重量stones[i-1]有两种决策不选最大重量为dp[i-1][j]。选前提是j stones[i-1]最大重量为dp[i-1][j - stones[i-1]] stones[i-1]。取两者较大值dp[i][j] max(dp[i-1][j], (j stones[i-1] ? dp[i-1][j - stones[i-1]] stones[i-1] : 0))。3. 初始化边界防护前0块石头无论容量多少最大总重量均为0因此dp[0][j] 0默认初始化为0即可。无需额外赋值。4. 填表顺序递推方向dp[i][j]依赖上一行dp[i-1][j]和dp[i-1][j - stones[i-1]]因此需要按行从上到下i从 1 到n列从左到右j从 1 到target遍历保证前置状态已就绪。5. 返回值目标映射设dp[n][target]为其中一堆能达到的最大重量不超过sum/2则另一堆重量为sum - dp[n][target]最终剩余重量为两者之差return (sum - dp[n][target]) - dp[n][target]即sum - 2 * dp[n][target]。三、代码class Solution { public: bool canPartition(vectorint nums) { // 1. 计算数组总和若为奇数则不可能平分 int sum 0; for (auto x : nums) sum x; if (sum % 2 ! 0) return false; int target sum / 2; // 目标子集和 int n nums.size(); // 2. 创建dp表 // dp[i][j] 表示能否从前 i 个元素中选取若干个数使其和恰好为 j vectorvectorbool dp(n 1, vectorbool(target 1, false)); // 3. 初始化 // 前 i 个元素中选出和为 0 的方案总是存在即什么都不选所以 dp[i][0] true for (int i 0; i n; i) { dp[i][0] true; } // 4. 填表顺序外层遍历物品i 从 1 到 n内层遍历容量j 从 1 到 target // 因为 dp[i][j] 依赖于 dp[i-1][j]不选当前数和 dp[i-1][j-nums[i-1]]选当前数 // 所以按行从上到下、列从左到右即可。 for (int i 1; i n; i) { for (int j 1; j target; j) { // 5. 状态转移方程 // 不选第 i 个数继承上一行的状态 dp[i-1][j] // 选第 i 个数前提是 j nums[i-1]且 dp[i-1][j-nums[i-1]] 为 true dp[i][j] dp[i - 1][j]; if (j nums[i - 1]) { dp[i][j] dp[i][j] || dp[i - 1][j - nums[i - 1]]; } } } // 6. 返回值dp[n][target] 表示能否从前 n 个数中选出和为 target 的子集 return dp[n][target]; } };四、流程图五、优化状态转移方程对于当前石头stones[i-1]第i个有两种决策不选最大重量不变即dp[j]保持上一轮的值。选前提是j stones[i-1]最大重量为上一轮dp[j - stones[i-1]] stones[i-1]。取两者较大值dp[j] max(dp[j], dp[j - stones[i-1]] stones[i-1])当j stones[i-1]时。等号右边的dp[j]和dp[j - stones[i-1]]均代表上一轮未处理当前石头的状态这正是逆序遍历保证的。填表顺序外层循环遍历每块石头i从 1 到n内层循环必须逆序遍历容量j从target到stones[i-1]。为什么要倒序因为dp[j]的更新依赖dp[j - stones[i-1]]这个值必须是上一轮未处理当前石头的状态才能保证每块石头最多被选一次01 背包性质。如果采用正序dp[j - stones[i-1]]可能已经在当前石头的处理中被提前更新导致石头被重复使用结果错误。为什么j只降到stones[i-1]当j stones[i-1]时无法选取当前石头dp[j]保持原值无需更新因此可以缩小遍历范围减少无用计算。class Solution { public: int lastStoneWeightII(vectorint stones) { int sum 0; for (auto x : stones) sum x; int target sum / 2; int n stones.size(); // 一维滚动数组 dp[j]替代原来的 dp[i][j]只保留“当前物品处理后的状态” vectorint dp(target 1, 0); for (int i 1; i n; i) { // 倒序遍历容量 j确保 dp[j - stones[i-1]] 是上一轮未选当前物品的值 // 避免同一物品被重复选取0/1背包特性。 // 下界为 stones[i-1]容量不足时无需更新直接继承旧值。 for (int j target; j stones[i - 1]; j--) { // 状态转移直接在一维数组上原地更新 // dp[j] max(不选当前物品的旧值, 选当前物品的新值) dp[j] max(dp[j], dp[j - stones[i - 1]] stones[i - 1]); } } // 结果计算与二维版本一致 int b sum - dp[target]; return b - dp[target]; } };