1049-最后一块石头的重量 II(Last Stone Weight II)
发表于：2021-12-03 | 分类： 中等
字数统计: 327 | 阅读时长: 1分钟 | 阅读量：

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

英文原文

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones 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 destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

Input: stones = [31,26,33,21,40]
Output: 5

Example 3:

Input: stones = [1,2]
Output: 1

 

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

中文题目

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

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

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

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

 

示例 1：

输入：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：

输入：stones = [31,26,33,21,40]
输出：5

示例 3：

输入：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$ 的最大价值。

每个物品都有「选」和「不选」两种决策，转移方程为：

$$f[i][j] = \max(f[i - 1][j], f[i - 1][j - stones[i - 1]] + stones[i - 1])$$

与完全背包不同，01 背包的几种空间优化是不存在时间复杂度上的优化，因此写成 朴素二维、滚动数组、一维优化 都可以。

建议直接上手写「一维空间优化」版本，是其他背包问题的基础。

代码：

[]
class 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]);
    }
}
[]
class 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]);
    }
}
[]
class 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 * \sum_{i = 0}^{n - 1} stones[i])$
  • 空间复杂度：$O(n * \sum_{i = 0}^{n - 1} stones[i])$

补充

在「基本分析」部分，我们证明出了「每一种合并方案」都能对应出「一个计算表达式」。

那么由原数组 $stones$ 中的数字，配合 $+/-$ 运算符构造出的任意「计算表达式」是否都能对应到「合法的合并方案」呢？

答案显然是不可以的，因为我们不能对所有数值都应用同一类符号。即最终答案范围必然落在 $[0, sum]$ 内。

但为什么做法是正确的？这就要配合我们「动态规划」部分去看了。

在「动态规划」部分，我们实际是将「计算表达式」中的负数部分提取公因数 $-1$，同时限定了这个部分的总和「最多不超过」$\frac{sum}{2}$，因此必然存在足够的剩余石子，将 DP 部分的石子“合并”掉，即整个合并过程（表达式计算过程）不会出现“负数”的中间结果。必然是一个「合法的合并方案」。

所以在这个前提下，我们不是在「所有表达式中找最优」，而是在「所有能够对应“合法合并方案”的表达式中找最优」。

由此，我们也知道最终 return 部分使用到的 abs 也是可以去掉的（因为人为确保了 DP 部分的「负号堆」总和不超过 $\frac{sum}{2}$，必然不会出现负数，保留初衷是为了与题解文字部分保持一致）。

背包问题（目录）

  1. 01背包 : 背包问题 第一讲

    1. 【练习】01背包 : 背包问题 第二讲（416. 分割等和子集）

    2. 【学习&练习】01背包 : 背包问题 第三讲（416. 分割等和子集）

    3. 【练习】01背包变形 : 背包问题 第 * 讲（1049. 最后一块石头的重量 II）

  1. 完全背包 : 背包问题 第四讲

    1. 【练习】完全背包 : 背包问题 第五讲（279. 完全平方数）
    2. 【练习】完全背包 : 背包问题 第六讲（322. 零钱兑换）
    3. 【练习】完全背包 : 背包问题 第七讲（518. 零钱兑换 II）

  2. 多重背包 : 背包问题 第八讲

  1. 多重背包（优化篇）

    1. 多重背包（优化篇）: 背包问题 第九讲
    2. 多重背包（优化篇）: 背包问题 第十讲

  2. 混合背包 : 背包问题 第十一讲

    1. 【练习】混合背包

  3. 分组背包

    1. 【练习】分组背包

  4. 多维背包

    1. 【练习】多维背包 : 背包问题 第 * 讲（474. 一和零）
    2. 【练习】多维背包 : 背包问题 第 * 讲（879. 盈利计划）

  1. 树形背包

    1. 【练习】树形背包

  2. 背包求方案数

    1. 【练习】背包求方案数 : 背包问题 第 * 讲（494. 目标和）
    2. 【练习】背包求方案数 : 背包问题 第 * 讲（879. 盈利计划）
  1. 背包求具体方案

  1. 泛化背包

    1. 【练习】泛化背包

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
46311 71374 64.9%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
动态规划 数组
上一篇:
1048-最长字符串链(Longest String Chain)
下一篇:
1163-按字典序排在最后的子串(Last Substring in Lexicographical Order)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo