题目：最后一块石头的重量 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

来源：力扣（LeetCode）第1049题

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

分析：

这道题一开始看好像没有什么思路，我们不妨把问题抽象出来。
题目要求最后把两块石头撞完后，剩下的重量要最小。那我们怎么才能让重量最小呢？这是关键点。
我们发现，只要每次相撞的两块石头，他们的大小都差不多，那么他们相撞之后得到的重量肯定是最小的。
因此，我们不妨把整个石子分成两块，只要我们把这两堆石子分的重量越接近，那么撞出来的重量一定会最小。
有人可能会想如果两边石子的数量不一样怎么办？不管两边数量有多不平衡，你都可以用一堆去撞另一堆，一定会把其中一堆装完的。
至此，我们把目的改一改，我们现在要找出两堆石子，他们的重量最接近。
如何找呢？
我们把所有石子的重量和算一下，然后除以一半，最好的情况下正好分成了两堆重量一样的石子，直接撞完就等于0了。
如果不行呢？
我们把石子的总重量叫sum,把一半的重量叫half。
我们一定能找到其中一堆小于half的(不管这一堆长度是多少，一定能找到),那么另一堆的重量肯定是大于half的。
所以我们只要找到一堆越接近half就行了，如果等于half最好。
参考LeetCode第416题，分割等和子集。
我们这次不是要分割等和子集，而是要找到越接近half的子集。
设置两个状态，见第一个代码。第一个是当前的位置，第二个是求得的和。
每次判断当前的和是否达到，有两种选择，使用这个位置，或者不使用这个位置。
进阶：我们可以使用dfs改写这段dp，从half开始，依次往0判断能否组成这个和，如果能那么这个和就是最大和。dfs更加快，因为只要找到最大和就直接返回答案就行了，不用再算下去。
进阶2：我们把dp变为一维dp，去掉当前位置的状态，只保留求得的和，问题转化为一个经典的0-1背包问题。

代码：

常规二维dp：

class Solution {
public int lastStoneWeightII(int[] stones) {
    int len = stones.length;
    int sum = 0;
    for (int stone : stones) sum += stone;
    int half = sum / 2;
    boolean[][] dp = new boolean[len][half+1];
    int max = 0;
    for (int i = 0; i < len; i++) {
        if (stones[i] <= half) {
            dp[i][stones[i]] = true;
            max = Math.max(max, stones[i]);
        }
    }
        
    for (int i = 1; i < len; i++) {
        for (int j = 1; j <= half; j++) {
            if (dp[i][j] == false) {
                if (stones[i] <= j) dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]];
                else dp[i][j] = dp[i-1][j];
            }
            if (dp[i][j]) max = Math.max(max, j);
        }
    }
    return sum - max - max;
}
}

dfs,三者最快的方法。没有加记忆化是因为数据量不大，加了之后可以更快。

class Solution {
int len;
public int lastStoneWeightII(int[] stones) {
    len = stones.length;
    int sum = 0;
    for (int stone : stones) sum += stone;
    int half = sum >> 1;
    for (int i = half; i >= 0; i--) {
        if (dfs(stones, 0, i, 0)) return sum - 2 * i;
    }
    return 0;
}

public boolean dfs(int[] stones, int ind, int sum, int target) {
    if (target == sum) return true;
    if (target > sum) return false;
    if (ind == len) return false;
    return dfs(stones, ind + 1, sum, target + stones[ind]) || dfs(stones, ind + 1, sum, target);
}
}

一维dp，由于少了一维，比二维dp要快一点。码量也最少。

class Solution {
public int lastStoneWeightII(int[] stones) {
    int len = stones.length;
    int sum = 0;
    for (int stone : stones) sum += stone;
    int half = sum / 2;
    int[] dp = new int[half+1];
    for (int stone : stones) {
        for (int i = half; i >= stone; i--) {
            dp[i] = Math.max(dp[i], dp[i-stone] + stone);
        }
    }
    return sum - dp[half] - dp[half];
}
}