LC 1049. 最后一块石头的重量 II
题目描述
这是 LeetCode 上的 1049. 最后一块石头的重量 II ，难度为 中等。
有一堆石头，用整数数组 stones 表示。
其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头最小的可能重量 。
如果没有石头剩下，就返回 0。
示例 1：1
2
3
4
5
6
7输入：stones = [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]，这就是最优值。
示例 2：1
2输入：stones = [31,26,33,21,40]
输出：5
示例 3：1
2输入：stones = [1,2]
输出：1
提示：
- $1 <= stones.length <= 30$
- $1 <= stones[i] <= 100$
基本分析
看到标题，心里咯噔了一下 🤣
一般性的石子合并问题通常是只能操作相邻的两个石子，要么是「区间 DP」要么是「四边形不等式」，怎么到 LeetCode 就成了中等难度的题目（也太卷了 🤣
仔细看了一下题目，可对任意石子进行操作，重放回的重量也不是操作石子的总和，而是操作石子的差值。
哦，那没事了 ~ 🤣
也是基于此启发，我们可以这样进行分析。
假设想要得到最优解，我们需要按照如下顺序操作石子：$[(sa, sb), (sc, sd), … ,(si, sj), (sp, sq)]$。
其中 $abcdijpq$ 代表了石子编号，字母顺序不代表编号的大小关系。
如果不考虑「有放回」的操作的话，我们可以划分为两个石子堆（正号堆/负号堆）：
- 将每次操作中「重量较大」的石子放到「正号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 $+$ 运算符
- 将每次操作中「重量较少/相等」的石子放到「负号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 $-$ 运算符
这意味我们最终得到的结果，可以为原来 $stones$ 数组中的数字添加 $+/-$ 符号，所形成的「计算表达式」所表示。
那有放回的石子重量如何考虑？
其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」。
什么意思呢？
假设有起始石子 $a$ 和 $b$，且两者重量关系为 $a \geq b$，那么首先会将 $a$ 放入「正号堆」，将 $b$ 放入「负号堆」。重放回操作可以看作产生一个新的重量为 $a - b$ 的“虚拟石子”，将来这个“虚拟石子”也会参与某次合并操作，也会被添加 $+/-$ 符号：
- 当对“虚拟石子”添加 $+$ 符号，即可 $+(a - b)$，展开后为 $a - b$，即起始石子 $a$ 和 $b$ 所在「石子堆」不变
- 当对“虚拟石子”添加 $-$ 符号，即可 $-(a - b)$，展开后为 $b - a$，即起始石子 $a$ 和 $b$ 所在「石子堆」交换
因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。
综上，即使是包含「有放回」操作，最终的结果仍然可以使用「为原来 $stones$ 数组中的数字添加 $+/-$ 符号，形成的“计算表达式”」所表示。
动态规划
有了上述分析后，问题转换为：为 $stones$ 中的每个数字添加 $+/-$，使得形成的「计算表达式」结果绝对值最小。
与（题解）494. 目标和 类似，需要考虑正负号两边时，其实只需要考虑一边就可以了，使用总和 $sum$ 减去决策出来的结果，就能得到另外一边的结果。
同时，由于想要「计算表达式」结果绝对值，因此我们需要将石子划分为差值最小的两个堆。
其实就是对「计算表达式」中带 $-$ 的数值提取公因数 $-1$，进一步转换为两堆石子相减总和，绝对值最小。
这就将问题彻底切换为 01 背包问题：从 $stones$ 数组中选择，凑成总和不超过 $\frac{sum}{2}$ 的最大价值。
其中「成本」&「价值」均为数值本身。
整理一下：
定义 $f[i][j]$ 代表考虑前 $i$ 个物品（数值），凑成总和不超过 $j$ 的最大价值。
每个物品都有「选」和「不选」两种决策，转移方程为：
与完全背包不同，01 背包的几种空间优化是不存在时间复杂度上的优化，因此写成 朴素二维、滚动数组、一维优化 都可以。
建议直接上手写「一维空间优化」版本，是其他背包问题的基础。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[][] f = new int[n + 1][t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
for (int j = 0; j <= t; j++) {
f[i][j] = f[i - 1][j];
if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
}
}
return Math.abs(sum - f[n][t] - f[n][t]);
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[][] f = new int[2][t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
int a = i & 1, b = (i - 1) & 1;
for (int j = 0; j <= t; j++) {
f[a][j] = f[b][j];
if (j >= x) f[a][j] = Math.max(f[a][j], f[b][j - x] + x);
}
}
return Math.abs(sum - f[n&1][t] - f[n&1][t]);
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[] f = new int[t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
for (int j = t; j >= x; j--) {
f[j] = Math.max(f[j], f[j - x] + x);
}
}
return Math.abs(sum - f[t] - f[t]);
}
}
- 时间复杂度：$O(n \times \sum_{i = 0}^{n - 1} stones[i])$
- 空间复杂度：$O(n \times \sum_{i = 0}^{n - 1} stones[i])$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1049 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
