[LeetCode] 1049. Last Stone Weight II

[grandyang]

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return  the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

Input: stones = [31,26,33,21,40]
Output: 5

Example 3:

Input: stones = [1,2]
Output: 1

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

这道题是之前那道 Last Stone Weight 的拓展，之前那道题说是每次取两个最大的进行碰撞，问最后剩下的重量。而这里是可以任意取两个石头进行碰撞，并且需要最后剩余的重量最小，这种玩数组求极值的题十有八九都是用动态规划 Dynamic Programming 来做的。首先来考虑 dp 数组该如何定义，若是直接用 dp[i] 来表示区间 [0, i] 内的石头碰撞后剩余的最小重量，状态转移方程将十分难推导，因为石子是任意选的，当前的 dp 值和之前的没有太大的联系。这里需要重新考虑 dp 数组的定义，这道题的解法其实挺难想的，需要转换一下思维，虽说是求碰撞后剩余的重量，但实际上可以看成是要将石子分为两堆，且尽可能让二者的重量之和最接近。若分为的两堆重量相等，则相互碰撞后最终将直接湮灭，剩余为0；若不相等，则剩余的重量就是两堆石子的重量之差。这道题给的数据范围是石子个数不超过 30 个，每个的重量不超过 100，这样的话总共的石子重量不超过 3000，分为两堆的话，每堆的重量不超过 1500。我们应该将 dp[i] 定义为数组中的石子是否能组成重量为i的一堆，数组大小设为 1501 即可，且 dp[0] 初始化为 true。这里的状态转移的思路跟之前那道 Coin Change 是很相似的，遍历每个石头，累加当前石头重量到 sum，然后从 1500 和 sum 中的较小值开始遍历（因为每堆的总重量不超过 1500），且i要大于 stone，小于当前石头的i不需要更新，由于当前的石头重量 stone 知道了，那么假如 i-stone 的 dp 值为 true 的话，则 dp[i] 也一定为 true。更新完成之后，从 sum/2 开始遍历，假如其 dp 值为 true，则用总重量 sum 减去当前重量的2倍，就是二堆石头重量的差值了，也就是碰撞后的剩余重量了，参见代码如下：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<bool> dp(1501);
        dp[0] = true;
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
            for (int i = min(1500, sum); i >= stone; --i) {
                dp[i] = dp[i] || dp[i - stone];
            }
        }
        for (int i = sum / 2; i >= 0; --i) {
            if (dp[i]) return sum - 2 * i;
        }
        return 0;
    }
};

Github 同步地址:

#1049

类似题目：

Last Stone Weight

Coin Change

参考资料：

https://leetcode.com/problems/last-stone-weight-ii/

https://leetcode.com/problems/last-stone-weight-ii/discuss/294888/JavaC%2B%2BPython-Easy-Knapsacks-DP

https://leetcode.com/problems/last-stone-weight-ii/discuss/295167/Java-beat-100-with-nice-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

标准的knapsack 0/1 problem