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

力扣传送门(opens new window)

题目难度：中等

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

输入：[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]，这就是最优值。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

解题思路：

分析：

我们由题目可以知道经过n次粉碎后，最终最多只会剩下1个石头，并且我们需要让最后一块石头的质量最小
我们继续分析可以发现（关键）：我们可以将这一堆石头分成两堆（heap1和heap2）
我们不妨设 heap1总质量 >= heap2总质量，而最后的结果就是heap1 - heap2，我们只需要保证heap1 - heap2最小即可

如何计算：

我们可以先求出这一堆石头的总质量sum，
而sum = heap1 + heap2 （heap1 > heap2）
heap1 - heap2 = sum - 2 * heap2
要求heap1 - heap2 的最小值，就可以转化成求sum - 2 * heap2 的最小值，
也就转化成了求 2 * heap2 的最大值，也就是求heap2的最大值（前提：sum - 2 * heap2 >= 0 等价于 heap2 <= sum / 2）
那么就转化成了01背包问题：背包的最大容量为 sum / 2

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

是不是感觉和 416. 分割等和子集非常像了。

本题物品的重量为stones[i]，物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和物品价值value[i]。

确定dp数组以及下标的含义

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。

可以回忆一下01背包中，dp[j]的含义，容量为j的背包，最多可以装的价值为 dp[j]。

相对于 01背包，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

一些同学可能看到这dp[j - stones[i]] + stones[i]中又有- stones[i] 又有+stones[i]，看着有点晕乎。

大家可以再去看 dp[j]的含义。

dp数组如何初始化

既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。

而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

当然也可以把石头遍历一遍，计算出石头总重量然后除2，得到dp数组的大小。

我这里就直接用15000了。

接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。

确定遍历顺序

物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

代码实现：

/**
 * 1049. Last Stone Weight II
 * 最后一块石头的重量 II
 */
public class LastStoneWeightII {
    public int lastStoneWeightII(int[] stones) {
        if(stones == null || stones.length == 0){
            return 0;
        }
        int sum = 0;
        for(int item : stones){
            sum+= item;
        }
        int target = sum >> 1;
        int[] dp = new int[target+1];
        //遍历石头
        for(int i = 0;i < stones.length;i++){
            for(int j = target;j >= stones[i];j--){
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }
}

代码跟踪：

让我们来计算一个简单的例子 [2, 4, 1, 1]。

对于给定的石头重量列表 [2, 4, 1, 1]，我们将按照之前的方法计算 dp 数组。

首先，我们需要计算石头的总重量。在这个例子中，总重量为 2 + 4 + 1 + 1 = 8。

此时target = (2 + 4 + 1 + 1)/2 = 4

然后，我们需要创建一个长度为 (总重量 + 1) / 2 = (8 + 1) / 2 = 4.5，但由于数组长度必须为整数，我们将其取整为 4 的数组 dp，并将其所有元素初始化为 0。

现在，我们开始计算 dp 数组。

对于第一个石头 2：

内层循环从 target = 4 递减到 2：
- j = 4，dp[4] = max(dp[4], dp[4 - 2] + 2) = max(0, dp[2] + 2) = 2
- j = 3，dp[3] = max(dp[3], dp[3 - 2] + 2) = max(0, dp[1] + 2) = 2
- j = 2，dp[2] = max(dp[2], dp[2 - 2] + 2) = max(0, dp[0] + 2) = 2

对于第二个石头 4：

内层循环从 target = 4 递减到 4：
- j = 4，dp[4] = max(dp[4], dp[4 - 4] + 4) = max(2, dp[0] + 4) = 4

对于第三个石头 1：

内层循环从 target = 4 递减到 1：
- j = 4，dp[4] = max(dp[4], dp[4 - 1] + 1) = max(4, dp[3] + 1) = 4
- j = 3，dp[3] = max(dp[3], dp[3 - 1] + 1) = max(2, dp[2] + 1) = 3
- j = 2，dp[2] = max(dp[2], dp[2 - 1] + 1) = max(2, dp[1] + 1) = 2
- j = 1，dp[1] = max(dp[1], dp[1 - 1] + 1) = max(0, dp[0] + 1) = 1

对于第四个石头 1：

内层循环从 target = 4 递减到 1：
- j = 4，dp[4] = max(dp[4], dp[4 - 1] + 1) = max(4, dp[3] + 1) = 4
- j = 3，dp[3] = max(dp[3], dp[3 - 1] + 1) = max(3, dp[2] + 1) = 3
- j = 2，dp[2] = max(dp[2], dp[2 - 1] + 1) = max(2, dp[1] + 1) = 2
- j = 1，dp[1] = max(dp[1], dp[1 - 1] + 1) = max(1, dp[0] + 1) = 1

完成计算后，dp 数组为 [0，1，2，3，4]。

根据题目要求，我们需要找到总重量之差最小的两堆石头，因此我们要从 dp 数组的后半部分开始寻找最接近 target 的值。在这个例子中，dp[4] = 4 是最接近 target = 4 的值。

因此，总重量之差最小的两堆石头的重量之差为 4 - 4 = 0。

时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
空间复杂度：O(m)

目录CONTENT

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

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

解题思路：

分析：

如何计算：

代码实现：

代码跟踪：

评论区