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

2026-09-07 HGNULB 约 6 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

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

题意分析

有一堆石头，每次任选两块重量分别为 $x$ 和 $y$ 的石头对撞：若 $x = y$ 两块都碎掉；若 $x < y$ 则重量为 $x$ 的碎掉，另一块变成 $y - x$。一直撞到最多剩一块，问剩下那块最小可能是多少，若全碎则返回 0。

要点是「任选两块」——撞击的先后顺序和配对方式完全由我们决定，题目问的是所有决策方案中的最小值，而不是某种固定策略的结果。

约束信号：石头数量不超过 30，每块重量不超过 100，因此总重量不超过 3000。数量很小但 $2^{30}$ 约十亿，暴力枚举全部子集在临界线上；而总重量只有 3000，说明按「重量」开状态是划算的。

边界情况：只有一块石头时它无法参与撞击，答案就是它自身的重量；总重量为偶数且能恰好平分时答案为 0；所有重量均为正，不存在零重量石头。

解法：0/1 背包接近半和

核心思路

每次碰撞都把两个重量 $x,y$ 合成 $\lvert x-y\rvert$。把完整过程展开成一棵二叉表达式树，叶子是原石头，内部节点是“作差后取绝对值”；展开根节点后，每块石头的系数只能是 $+1$ 或 $-1$。因此最终重量可写成
\[\left\lvert \sum_{i=1}^{n}\varepsilon_i \cdot stones_i \right\rvert,\qquad \varepsilon_i\in\{-1,+1\}.\]
这相当于把石头分成正、负两组。设总重量为 $S$，其中一组的和为 $x$，两组之差就是 $\lvert S-2x\rvert$。

这个转换不只是必要条件，也能覆盖最优答案。对一个最优分组，始终从两组各取一块碰撞，并把差值归到较重石头所在组，组间差保持不变。若一组清空后另一组还剩至少两块，把其中较小的残块整体换组会得到更小的差，与原分组最优矛盾。因此过程最终只会剩一块（或全部抵消），其重量正是最小分组差。

两组地位对称，只需考虑 $x\le \lfloor S/2\rfloor$。此时 $S-2x$ 随 $x$ 增大而减小，所以目标变为：从石头中选出若干块，使总重量不超过 $target=\lfloor S/2\rfloor$ 且尽量大。这就是每块物品只能选择一次的 0/1 背包。

定义 dp[c] 为处理完当前这些石头后，容量不超过 c 时能取得的最大重量。加入重量 w 时：
\[dp[c]=\max\bigl(dp[c],\ dp[c-w]+w\bigr).\]
容量必须从大到小更新，保证右侧的 dp[c-w] 仍是加入当前石头前的状态，同一块石头不会被重复选择。最终答案是 S - 2 * dp[target]。

正确性依据：

上面的符号分组证明说明，最优碰撞结果等于最小两组重量差。

归纳可知，处理前 $i$ 块石头后，dp[c] 恰是这 $i$ 块中不超过 c 的最大子集和：不选第 $i$ 块保留旧值，选择它则由 dp[c-w] + w 得到。

在 $x\le S/2$ 的范围内，最大化 $x$ 等价于最小化 $S-2x$，所以返回式得到全局最优答案。

解题步骤

求所有石头的总重量 sum，令 target = sum / 2。

创建长度为 target + 1 的 dp 数组；初值 0 表示什么都不选。

依次处理每块石头 stone，让容量从 target 倒序遍历到 stone。

用 dp[cap - stone] + stone 尝试更新 dp[cap]。

返回 sum - 2 * dp[target]。

以 [2,7,4,1,8,1] 为例：总和 $S=23$，背包容量为 11。背包能选出 $7+4=11$，另一组和为 12，因此最小剩余重量为 $23-2\times11=1$。无需模拟具体碰撞顺序。

代码实现

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

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

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, stone := range stones {
        sum += stone
    }

    target := sum / 2
    dp := make([]int, target+1)
    for _, stone := range stones {
        for cap := target; cap >= stone; cap-- {
            candidate := dp[cap-stone] + stone
            if candidate > dp[cap] {
                dp[cap] = candidate
            }
        }
    }
    return sum - 2*dp[target]
}

复杂度分析

设石头数量为 $n$，总重量为 $S$，背包容量 $target=\lfloor S/2\rfloor$。

时间复杂度：$O(n\cdot target)=O(nS)$。

空间复杂度：$O(target)=O(S)$。

关键点总结

碰撞过程的本质是给每块石头分配正负号，最终值对应两组重量差。

两组对称，只需寻找不超过总和一半的最大子集和。

dp[c] 表示“不超过容量”的最优值，不要求恰好装满，因此可全部初始化为 0。

0/1 背包必须倒序枚举容量；正序会把一块石头重复使用。

面试时应讲清“过程模型 → 分组差 → 半和背包”三步，而不是直接套背包模板。

易错点总结

误用最大堆贪心：每次撞最重的两块只保证当前差小，不保证最终最优。例如 [31,26,33,21,40]，贪心得到 9，而最优答案是 5。

容量正序更新：[1,5] 中处理石头 1 时会把它重复装入容量 2、3，错误得到答案 0；倒序才能保持 0/1 语义。

容量向上取整：若 target = (sum + 1) / 2，[1,2] 会选到 2 并返回 $3-4=-1$。必须取下整，使所选组不超过半和。

写成恰好装满背包：本题只需最接近半和，容量未必能恰好达到；使用不可达哨兵反而容易漏掉正确子集。

返回值少减一组：答案是两组之差 sum - 2 * dp[target]，不是 dp[target] 或 sum - dp[target]。

把碰撞顺序当状态搜索：每步都会产生新重量，分支多且状态难去重；符号分组后状态只剩“当前可达重量”。

相似题目

题目	难度	考察点
416. 分割等和子集	中等	只需判断能否恰好装满半和，布尔背包即可
494. 目标和	中等	同为符号分配模型，但求方案数而非最值
474. 一和零	中等	二维容量约束，需嵌套两层倒序循环
879. 盈利计划	困难	一维是人数上限、一维是利润下限，方向相反
LCR 101. 分割等和子集	简单	416 的同题改编，可直接复用布尔背包模板
LCR 102. 目标和	中等	494 的同题改编，重点在负数目标的可行性判断