题目链接

英文链接：https://leetcode.com/problems/last-stone-weight-ii/

中文链接：https://leetcode-cn.com/problems/last-stone-weight-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 <= stones.length <= 30
1 <= stones[i] <= 1000

题目详解

LeetCode1046-最后一块石头的重量属于贪心算法，每次选最重的两块石头即可，本题与之无关。
合并的过程就是给每个重量前加上正号或负号的过程，相当于把这些石头分为两组，使得两组石头的重量总和差值尽可能地小。显然，这是一个 01 背包问题，类似于 LeetCode494-目标和。
用 f[i] 表示是否存在一个划分，使得某组的重量总和为 i。
初始化 f[0] = true，其余为 false。
每个物品有选或不选两种选择，状态转移方程为 f[i] = f[i] | f[i - stone]。
可以只用统计较小的一组重量总和，另一组重量总和可以由全体石头重量总和做差与当前重量总和得到。
最后遍历 f，若 f[i] == true，说明存在当前重量总和为 i，另一组重量总和为 sum - i，二者之差 sum - i - i 就是结果。为了达到最小值，i 从大到小遍历。

public class LeetCode_01049 {

    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int n = sum >> 1;
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for (int stone : stones) {
            for (int i = n; i >= stone; --i) {
                f[i] = f[i] | f[i - stone];
            }
        }
        for (int i = n; i >= 0; --i) {
            if (f[i]) {
                return sum - 2 * i;
            }
        }
        return sum;
    }
}

可以换一种方式进行动态规划。
用 f[i] 表示石头组成的不超过 i 的最大总重量。
初始化所有 f[i] = 0。
状态转移方程为 f[i] = Math.max(f[i], f[i - stone] + stone)。
记 n 为总重量的一半，则 f[n] 表示较小的一组重量总和，sum - f[n] 表示较大的一组重量总和，二者之差就是结果。

public class LeetCode_01049 {

    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int n = sum >> 1;
        int[] f = new int[n + 1];
        for (int stone : stones) {
            for (int i = n; i >= stone; --i) {
                f[i] = Math.max(f[i], f[i - stone] + stone);
            }
        }
        return sum - 2 * f[n];
    }
}