LC1049. 最后一块石头的重量II

题目描述

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 示例 1： 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。 示例 2： 输入：stones = [31,26,33,21,40] 输出：5 提示： 1 <= stones.length <= 30 1 <= stones[i] <= 100

题目解析

好的，没问题！我是 AlgoMooc 的算法老师，咱们今天就用最通俗易懂的方式，把这道题给它彻底讲明白。别怕，跟着我一步步来，你一定能学会。

题目在说什么

想象一下，你面前有一堆石头，每个石头都有自己的重量。现在，游戏规则是这样的：

1. 你每次可以随便挑出两块石头。 2. 把它们放在一起“对撞”粉碎。

• 如果两块石头一样重，那它们就同归于尽，都变成粉末消失了。
• 如果不一样重，轻的那块会被彻底粉碎，而重的那块呢，会变轻，新的重量就是它俩的重量差。

3. 你一直重复这个过程，直到最后，最多只剩下一块石头。

题目问的是：最后剩下的这块石头，它的重量最小可能是多少？ 如果最后一块都不剩（全部同归于尽），那答案就是 0。

你看示例 1，一堆石头 [2,7,4,1,8,1]，通过一系列操作，最后能只剩下一块重量为 1 的石头。这就是最优解。

思路是怎么来的

这个问题看起来有点复杂，对吧？别急，我们换个角度来想。

第一步：把“粉碎”看成“做减法”

你看，每次粉碎操作，是不是有点像在做减法？ y - x。如果我们把整个过程看成一系列连续的减法，最后剩下的那块石头，其实就是所有石头重量经过加减运算后的结果。

比如示例 1 里，(8-7) + (4-2) + (1-1) 最后剩下 1。但注意，这个加减的顺序和组合方式，决定了最后的结果。

第二步：把“减法”看成“分组”

这里有一个非常巧妙的观察：任何一次粉碎操作，其实都可以理解为，我们把石头分成了“正”和“负”两组。

怎么理解呢？我们来看一个简单的例子。假设有三块石头：[a, b, c]。

• 方案一：先粉碎 a 和 b，得到 |a-b|，再和 c 粉碎，结果是 ||a-b| - c|。
• 方案二：换个顺序，先粉碎 a 和 c，得到 |a-c|，再和 b 粉碎，结果是 ||a-c| - b|。

你会发现，无论顺序怎么变，最后的结果，都可以写成类似 ±a ± b ± c 这种形式，只是每个石头前面的符号是正还是负，取决于它在这个加减链条里的位置。而且，所有符号加起来，必须等于 0 或者 ±某个值。

更关键的是：我们最终的目标是让这个结果最小，也就是让“正的那一堆”的总重量，和“负的那一堆”的总重量，尽可能接近。

为什么？因为最后剩下的石头重量 = |正堆总重 - 负堆总重|。如果两堆一样重，结果就是 0，完美！如果不一样，差值就是剩下的石头。

第三步：把问题变成“装背包”

好了，现在问题就变成了：我们有一堆石头，想把它分成两堆，让这两堆的重量差最小。

那怎么分呢？我们其实可以这样想：

1. 先算出所有石头的总重量 sum。 2. 我们只需要找到一堆石头，让它的总重量尽可能接近 `sum/2`，但不要超过 `sum/2`。 3. 为什么？因为如果这一堆的重量是 x，那么另一堆的重量就是 sum - x。两堆的差就是 |sum - x - x| = |sum - 2x|。为了让这个差值最小，我们当然希望 x 越接近 sum/2 越好。

所以，问题就变成了一个经典的 “0-1 背包问题”。

生活化的比喻：

想象你有一个背包，背包的容量是 sum/2。现在，你面前有一堆石头（物品），每个石头有自己的重量。你想往背包里装石头，目标是让背包里石头的总重量尽可能大，但不能超过背包的容量。

这个“背包里装的最大重量”，就是我们上面说的 x。找到了这个 x，答案 sum - 2x 就出来了。

代码逐步拆解

我们来看参考代码，把它拆解开，一步一步讲清楚。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 1. 计算总重量 sum
        int sum = 0;
        for (int num : stones) {
            sum += num;
        }

        // 2. 确定背包容量 target = sum / 2
        int target = sum / 2;

        // 3. 创建 DP 表格
        // dp[i][j] 的含义：考虑前 i 个石头（i 从 1 开始），在容量不超过 j 的情况下，能装的最大重量。
        int dp[][] = new int[stones.length + 1][target + 1];

        // 4. 开始填表
        for (int i = 1; i <= stones.length; i++) {
            for (int j = 0; j <= target; j++) {
                // 情况 A：当前石头太重了，背包放不下
                // 注意：stones[i-1] 是第 i 个石头的重量（因为数组索引从0开始）
                if (j < stones[i - 1]) {
                    // 那就不选这个石头，最大重量和之前 i-1 个石头一样
                    dp[i][j] = dp[i - 1][j];
                } 
                // 情况 B：背包能放下当前石头
                else {
                    // 我们有两个选择：
                    // 选择1：不拿这个石头，那么最大重量还是 dp[i-1][j]