1049. 最后一块石头的重量 II：01 背包问题 DP，附两大类背包问题的通用状态定义.md

题目简述：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

题目链接：1049. 最后一块石头的重量 II

思路

原表述有些掩盖本质，导致我最初除了万能的回溯算法没想到别的什么方案，但无剪枝的回溯算法在数据范围 1 <= stones.length <= 30 下是一定会报超时的。

我们去掉场景化的描述，本问题实际上是：

• 给你一个数组 nums，数组的总和的固定的，记为 sum(nums)，选取其中的部分元素，记这些元素的和为 partSum，那么你能让该和与剩余元素和的绝对差值，即 abs(sum(nums) - partSum) 最小吗？

现在就很显而易见了，这是针对每个元素的「选与不选」问题，要求计算一个仅依赖于选择方案的一个变量的最优化问题，这就是典型的「01 背包」，可以用动态规划高效求解。

既然可以用动态规划求解，当然也就可以继续考虑回溯算法了，但需要做与动态规划类似的状态定义，才方便进行记忆化搜索以剪枝。

标准的 01 背包模型中通常有两种状态的定义方式，考虑何种定义取决于问题本身是计算解的存在性还是一个最优化问题：

1. 针对解的存在性（不考虑价值），即提问是否存在一种选择方案恰使得总价值为目标值，通常定义布尔状态值 $dp[i][j]$，其中 $i$ 限定物体范围、$j$ 限定背包容量，$dp[i][j]$ 表示仅考虑索引 $i$ 及其之前的物品时，我们是否能够恰装满容量为 $j$ 的背包，代表问题是 416. 分割等和子集；
2. 针对最优化问题（最优化价值），即提问总价值或总价值的某个单调函数的最值，通常定义离散状态值 $dp[i][j]$，其中 $i$ 限定物体范围、$j$ 限定背包最大容量，$dp[i][j]$ 表示仅考虑索引 $i$ 及其之前的物品时、当背包容量最大为 $j$ 时，我们能够从背包里获得的最大价值，代表问题是 494. 目标和。

虽然本问题按描述看起来是一个关于 abs(sum(nums) - partSum) 的最优化问题，但函数 abs(sum(nums) - partSum) 的最优化并不好求解，所以我们考虑第一种状态值定义然后根据状态与状态值寻找所选取石头的重量最接近 sum(nums) / 2 的合法选择方案，而不是第二种状态值定义。

定义 $dp[i][j]$ 表示仅考虑自 stones[0] 起至 stones[i] 的石头且目标重量和为 $j$ 时，合法的选择方案是否存在，则状态转移方程为 $$ dp[i][j]=\underbrace{dp\big[i-1\big]\big[j-stones[i]\big]}{\text{selected}}\lor\underbrace{dp[i-1][j]}{\text{do not select}} $$ 初始化状态： $$ \forall i,\ \ dp[i][0]=\text{true} $$ 计算出 $dp$ 数组后，对于 $dp[i][*]$，我们找出与重量和 $\frac{\mathrm{sum}(stones)}{2}$ 最接近的合法选择方案（$dp[i][k]=\text{true}$，找出与 $\frac{\mathrm{sum}(stones)}{2}$ 最接近的 $k$），那么该方案的重量和 $k$ 与剩余石头重量和 $\mathrm{sum}(stones)-k$ 的绝对差值就是剩下石头的最小的可能重量。

代码

算法的时间复杂度为 $O(nS)$，如果存储完整的 $dp$ 数组则空间复杂度为 $O(nS)$，如果考虑滚动数组则空间复杂度为 $O(S)$。

存储完整的 $dp$ 数组，直观地复现分析中的逻辑：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int stone : stones) sum += stone;
        boolean[][] dp = new boolean[n + 1][sum + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = true;
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - stones[i - 1] >= 0) dp[i][j] = dp[i][j] || dp[i - 1][j - stones[i - 1]];
            }
        }

        int partSum = sum >> 1;
        while (!dp[n][partSum]) {
            partSum--;
        }

        return (sum - partSum) - partSum;
    }
}

滚动数组，注意 $dp[j]$ 的更新顺序：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int stone : stones) sum += stone;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = sum; j > 0; j--) {
                if (j - stones[i - 1] >= 0) dp[j] = dp[j] || dp[j - stones[i - 1]];
            }
        }

        int partSum = sum >> 1;
        while (!dp[partSum]) {
            partSum--;
        }

        return (sum - partSum) - partSum;
    }
}