1049. 最后一块石头的重量 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

这个问题可以转换为一个背包问题。具体来说，我们要将石头分成两组，使两组的重量尽量相等。

假设两组的重量分别为 S1 和 S2，且 S1 <= S2，我们的目标是使 S2 - S1 尽可能小。

设所有石头的总重量为 sum，我们知道： S1+S2=sum 我们希望 S2 - S1 尽可能小。由于 S1 <= S2，可以表示为： S2−S1=minimize

利用上面的两个公式可以得到： S2−S1=(sum−S1)−S1=sum−2×S1

动态规划-数组递推-转换为背包问题，

将石头分成两组，使两组的重量尽量相等。假设两组的重量分别为 S1 和 S2，且 S1 <= S2， 我们的目标是使 S2 - S1 尽可能小。遍历每块石头，遍历所有可能的重量。dp[i][j] 表示前 i 块石头是否能组成重量为 j 的子集。

S2−S1=(sum−S1)−S1=sum−2×S1，所以我们要找S1尽可能大且dp[i][S1]为true的S1，即S1必须是能由给定的石头组成。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        // 计算所有石头重量的总和
        for (int weight : stones) {
            sum += weight;
        }

        int n = stones.length, m = sum / 2; // S1不会超过sum/2，因为我们假设 S1<=S2
        // 初始化动态规划数组 dp，dp[i][j] 表示前 i 块石头（[0,i-1]）是否能组成重量为 j 的子集。注意i是长度不是索引，这样做的好处是初始化比较简单。
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true; // 初始状态，表示没有石头时可以组成重量为 0 的子集。重点。第一行和第一列的其余位置都是false。

        // 遍历每块石头。先硬币，再金额。
        for (int i = 0; i < n; ++i) {
            // 遍历可能的重量。注意最大值是sum/2
            for (int j = 0; j <= m; ++j) {
                if (j < stones[i]) {
                    // 当前重量 j 小于石头重量 stones[i]，则不能选i这块石头，因此从[0,i]里选等价于从[0,i-1]里选
                    dp[i + 1][j] = dp[i][j];
                } else {
                    // 当前重量 j 大于等于石头重量 stones[i]，可以选择或不选择这块石头
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }

        // 寻找最接近 sum/2 的重量 j。m=sum/2
        for (int j = m;; --j) {
            if (dp[n][j]) { // 计算dp数组的意义在这
                // 返回最后的最小可能重量，即总和减去两倍的 j
                return sum - 2 * j;
            }
        }
    }
}

滚动更新-倒序遍历

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        // 计算所有石头重量的总和
        for (int weight : stones) {
            sum += weight;
        }

        int m = sum / 2;
        // 初始化动态规划数组 dp，dp[j] 表示是否可以从石头集合中选取若干石头，使其总和为 j
        boolean[] dp = new boolean[m + 1];
        dp[0] = true; // 初始状态，表示可以从石头集合中选取若干石头使其总和为 0（即空集）

        // 遍历每块石头
        for (int weight : stones) {
            // 倒序遍历所有可能的重量，从 m 到 weight
            for (int j = m; j >= weight; --j) {
                // 更新 dp 数组，判断是否可以从石头集合中选取若干石头使其总和为 j
                dp[j] = dp[j] || dp[j - weight];
            }
        }

        // 从接近 sum/2 的最大值开始查找，找到一个 dp[j] 为 true 的值 j
        for (int j = m;; --j) {
            if (dp[j]) {
                // 返回最后的最小可能重量，即总和减去两倍的 j
                return sum - 2 * j;
            }
        }
    }
}