LEETCODE 1049. Last Stone Weight II 解题思路分析

题目大意：

最后一块石头的重量 II

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

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 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. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1049

解题思路分析：

题目说两个石头遇到之后，重量小的会消失，重量大的剩下两个石头的重量之差。如果俩石头一样重，则同时消失。最后求出所有石头相遇之后剩下的那一个石头重量的最小值。其实简单来说，就是把这一组石头的重量附上加减号，求和最小的可能。再换句话说，我们可以将石头分成两部分（都是正整数），两部分分别求和，这两个和的差值最小的情况即为最优解。

这样问题就转化为：是否能找到n个数，他们的和最接近整体和的一半。进而题目就变成了另外一题 LEETCODE 416. Partition Equal Subset Sum 。他们的思路完全相同。

很多人把这种题目称为背包问题， LEETCODE 416. Partition Equal Subset Sum 的解法就是背包问题的典型模板。解决这类问题的关键是求和，确切的说，是需要求出所有数字能够组成的和的可能，然后再从这些和中选出一个最接近目标值的数字（小于等于目标值）即为答案。

如何求和，我们来举例说明，比如存在数组：

int[] A = [1, 2, 3];

我们循环数组的每一个数，看看他们有多少组合的情况：

// 先从数组中取出1，这时组成的和只有1种结果。
int[] sum = [1]; // A = [2, 3];
// 然后取出2，这时2自身是一种结果，2+1是一种结果。
int[] sum = [1](之前的结果) + [2, 3(2+1)](新的结果); // A = [3];
// 再取出3，这时3自身是一种结果，3加上之前的每一个结果也是结果
int[] sum = [1, 2, 3](之前的结果) + [3, 4(3+1), 5(3+2), 6(3+3)](新的结果); // A = [];
// 即：
int[] sum = [1, 2, 3, 3, 4, 5, 6]

虽然最终sum中有重复的结果，但这不影响我们解决背包问题。

再回到本题，我们不需要求出所有可能的和，我们需要的是最接近总和一半的数字，因此，还以上边的A数组为例，我们只需要找到是否存在一些数字的和最接近3（如果没有再找2，直到找到为止）。找到之后，说明当前有一组数的和为3，那么剩下的数的和应该为(totalSum – 3)，进而两者的差值应该是 (totalSum – 3) – 3。

代码方面，我们使用一个dp数组来保存和出现的可能。

boolean[] dp;

其中dp[i]表示：是否存在一些数字的和为i。初始值dp[0]为true，i的最大值为数组总和的一半再加一（注意下标越界。因为我们需要dp数组长度为总和的一半）。

具体实现看下完整代码：

public int lastStoneWeightII(int[] stones) {
    int sum=0; // 先求总和
    for(int stone : stones){
        sum+=stone;
    }
    int target = sum / 2; // 求出总和的一半。我们的目标是找到一组数的和最接近target
    // 定义dp数组，长度为target+1
    // dp[i]表示，是否存在一组数的和为i
    boolean[] dp = new boolean[target+1];
    dp[0]=true;
    int max=0; // 最接近target的最大值
    for(int stone : stones){ // 循环所有石头的重量
        for(int i=target;i>=stone;i--){ // i代表重量和。
            // 当前石头重量为stone，如果存在(i-stone)这个和，
            // 那么(i-stone)+stone = i 也是一种和的可能。
            dp[i] = dp[i] || dp[i-stone];
            if(dp[i]){ // 如果存在一组数的和为i
                if(i==target){这个和等于target时，直接返回。
                    return sum - target - target;
                }
                max = Math.max(i, max); // 更新最近接target的最大值
            }
        }
    }
    return sum - max - max;
}

本题解法运行时间为1ms。

Runtime: 1 ms, faster than 99.12% of Java online submissions for Last Stone Weight II.

Memory Usage: 34 MB, less than 100.00% of Java online submissions for Last Stone Weight II.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1049-last-stone-weight-ii-解题思路分析/