LeetCode_120_LastStoneWeightII

1. question: 最后一块石头的重量II（中等）

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/last-stone-weight-ii

示例 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

2. answers

这道题最开始没想出来，本质上还是对问题本质没有分析清楚。

首先本问题是两块石头碰撞粉碎，剩余的是差值，仍然作为一块石头出现。那么假设，两个集合，每个集合中都包含若干块石头，两个集合中的石头碰撞，每一对石头碰撞后，剩余的差值返回重量大的石头所在的集合中。

显然，最终剩余的石头重量就是集合总和差值。

那么本题是所有石头，任意碰撞。其实，本质上可归结为两个集合进行碰撞。比如说，石头小的属于一个集合，石头大的属于一个集合。要想最终剩余的石头最小，显然两个集合的总和差值越小，即剩余石头就越小。

此时，问题可转化为划分两个子集，使得两个子集尽可能的相等（**即尽可能地接近总和/2**），既然是两个子集，那么肯定一个大，一个小，最优情况就是都是总和/2。

因此，和划分两个子集类似，石头的重量就是weight和value。设置target为总重量/2，定义一维动态数组dp[target]，表示在当前背包容量的基础上，当前石头以及前面石头所能达到的最大值。代码如下所示：

public class Solution_0120 {

    public int lastStoneWeightII(int[] stones) {

        int sums = 0;
        for (int stone : stones) {
            sums += stone;
        }

        // 取整
        int target = sums / 2;

        // 定义存储空间dp[j]，表示在J容量下，当前石头以及前面的石头所能形成的最大值。
        int[] dp = new int[target + 1];

        // 初始化第一个石头。
        for (int i = 0; i < target + 1; i++) {
            if(stones[0] <= i) dp[i] = stones[0];
        }

        // 动态规划，因为采用的是一维动态数组，所以逆序遍历
        for (int i = 1; i < stones.length; i++) {
            for (int j = target; j >= 0; j--) {

                if(stones[i] > j) dp[j] = dp[j];
                else dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        // 此时 dp[target] 就是所能形成的最优解。
        return Math.abs(sums - 2 * dp[target]);
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] stones = {2, 7, 4, 1, 8, 1};
        int[] stones = {31, 26, 33, 21, 40};

        Solution_0120 s = new Solution_0120();

        System.out.println(s.lastStoneWeightII(stones));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。