[Leetcode 1049] Last Stone Weight II

原题说明

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks 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 totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example 1:

Input: [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.

Note:

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

解题思路

假设有三个石头x1，x2, x3, 无论如何组合，最终都会成为三个数之间的加减法
比如如果先合并x1，x2,再与x3合并，则最终的重量为x3 - x1 + x2 (假设x1 > x2, x3 > (x1 - x2))
所以这道题相当于将数组分为两组，两组分别求和为S1和S2，并希望其差值(S2 - S1 if S2 >= S1)最小:
S1 + S2 = total_weight
if S1 <= S2 => S2 - S1 = total_weight - S1 - S1 = total_weight - 2 * S1
所以相当于我们希望较小的一半石头的重量和尽可能接近 total_weight / 2

我们通过动态规划来求解这道题，建立一个数组dp来记录石头重量之和的所有可能值:
dp[i]为true如果我们可以使得一组stones的重量之和S1等于i，反之则为false
我们遍历stones数组，用sum_weight来记录当前遍历到的所有重量之和，
我们判断加入当前的石头重量stone_weight后，从sum_weight到stone_weight之间的每一个值weight是否可能成为S1的值：
如果dp[weight - stone_weight]为true，则对应的dp[weight]也设为true。
遍历stones完成后，从weight = sum_weight / 2开始逐渐减小，如果dp[weight] = true,
则当前weight即我们希望寻找的S1的值，所以返回对应的total_weight - 2 * weight即可。

示例代码 (cpp)

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        // 由于限制条件：
        // 1 <= stones.length <= 30
        // 1 <= stones[i] <= 100
        // 所以石头重量总和最多为 30 * 100 = 3000
        vector<bool> dp(1501, false);
        dp[0] = true;
        int sum_weight = 0;
        for (const auto stone_weight : stones) {
            sum_weight += stone_weight;
            // 一定要用--，而不是++，不然同一块石头的重量会被视作可以反复利用
            // 比如如果stone_weight = 1, 用++的话，会使得dp的所有小于sum_weight的值都为true
            for (int weight = sum_weight; weight >= stone_weight; --weight) {
                if (dp[weight - stone_weight]) {
                    dp[weight] = true;
                }
            }
        }
        for (int weight = sum_weight / 2; weight >= 0; --weight) {
            if (dp[weight]) {
                return sum_weight - 2 * weight;
            }
        }
        return 0;
    }
};

示例代码 (java)

class Solution {
    public int lastStoneWeightII(int[] A) {
        boolean[] dp = new boolean[1501];
        dp[0] = true;
        int sumA = 0;
        for (int a : A) {
            sumA += a;
            for (int i = Math.min(1500, sumA); i >= a; --i)
                dp[i] |= dp[i - a];
        }
        for (int i = sumA / 2; i >= 0; --i)
            if (dp[i]) return sumA - i - i;
        return 0;
    }
}

示例代码 (python)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = {0}
        sumA = sum(stones)
        for stone in stones:
            dp |= {stone + i for i in dp}
        return min(abs(sumA - i - i) for i in dp)

复杂度分析

时间复杂度: O(N)
空间复杂度: O(total_weight)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！