问题描述

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.)

提供一个整数数组，每个元素代表一块石头的重量。

每次从中挑选两块石头然后将其粉碎，假设x <= y，粉碎规则如下：

• 如果x == y，那么两块石头均被完全粉碎。
• 如果x != y，那么轻的那块石头x就会被完全粉碎，而重量为y的石头变成y - x。

最后，最多会剩下一块石头，请返回其最小重量(如果没有石头剩下，则返回0)。

举个例子：

二维

Thanks @wzc1995{:target=”_blank”}

梳理下思路：

首先，我们求出数组元素总和的平均值t。

然后，进行DP，我们需要明确f(i, t)的含义：

它是一个boolean值，代表最多挑选i件商品，总价值是否能达到t。

最后，倒序遍历dp[l]数组，一旦遇到dp[l][i] = true，直接返回sum - 2 * i，否则返回sum。

来看下实现：

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        var dp = new boolean[l + 1][t + 1];
        dp[0][0] = true;

        for (int i = 1; i <= l; i++){
            dp[i][0] = true;
            for (int j = 1; j <= t; j++){
                // 有容量
                if (j - stones[i - 1] >= 0){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stones[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        for (int i = t; i >= 0; i--){
            if (dp[l][i]) return sum - 2 * i;
        }
        return sum;
    }
}

一维

来看下实现：

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        var dp = new boolean[t + 1];
        dp[0] = true;

        for (int s: stones){
            for (int j = t; j >= s; j--){
                dp[j] |= dp[j - s];
            }
        }

        for (int i = t; i >= 0; i--){
            if (dp[i]) return sum - 2 * i;
        }
        return sum;
    }
}

我们也可以在第一个循环中计算最大的中间值half：

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        int half = 0;
        var dp = new boolean[t + 1];
        dp[0] = true;

        for (int s: stones){
            for (int j = t; j >= s; j--){
                dp[j] |= dp[j - s];
                if (dp[j]) half = Math.max(half, j);
            }
        }

        return sum - 2 * half;
    }
}

Enjoy it !