[数据结构与算法]2021-10-7 1049. 最后一块石头的重量 II（背包问题+动态规划）

注：

题目：
有一堆石头，用整数数组 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

题解：
思路与算法
假设想要得到最优解，我们需要按照如下顺序操作石子：[(sa, sb), (sc, sd), … ,(si, sj), (sp, sq)]。

其中 abcdijpq代表了石子编号，字母顺序不代表编号的大小关系。

如果不考虑「有放回」的操作的话，我们可以划分为两个石子堆（正号堆/负号堆）：

• 将每次操作中「重量较大」的石子放到「正号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 + 运算符。
• 将每次操作中「重量较少/相等」的石子放到「负号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 ? 运算符。

这意味我们最终得到的结果，可以为原来 stonesstones 数组中的数字添加 +/? 符号，所形成的「计算表达式」所表示。

那有放回的石子重量如何考虑？

其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」。

什么意思呢？

假设有起始石子 a 和 b，且两者重量关系为 a≥b，那么首先会将 a 放入「正号堆」，将 b 放入「负号堆」。重放回操作可以看作产生一个新的重量为 a?b 的“虚拟石子”，将来这个“虚拟石子”也会参与某次合并操作，也会被添加 +/? 符号：

• 当对“虚拟石子”添加 + 符号，即可 +(a?b)，展开后为 a?b，即起始石子 a 和 b 所在「石子堆」不变
• 当对“虚拟石子”添加 ? 符号，即可 ?(a?b)，展开后为 b?a，即起始石子 a 和 b 所在「石子堆」交换

因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。

综上，即使是包含「有放回」操作，最终的结果仍然可以使用「为原来 stonesstones 数组中的数字添加 +/? 符号，形成的“计算表达式”」所表示。

有了上述分析后，问题转换为：为 stones 中的每个数字添加 +/?，使得形成的「计算表达式」结果绝对值最小。

需要考虑正负号两边时，其实只需要考虑一边就可以了，使用总和sum 减去决策出来的结果，就能得到另外一边的结果。

同时，由于想要「计算表达式」结果绝对值，因此我们需要将石子划分为差值最小的两个堆。

其实就是对「计算表达式」中带 ? 的数值提取公因数 ?1，进一步转换为两堆石子相减总和，绝对值最小。

这就将问题彻底切换为 1 背包问题：从 stones 数组中选择，凑成总和不超过 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 背包的几种空间优化是不存在时间复杂度上的优化，因此写成 朴素二维、滚动数组、一维优化 都可以。

复杂度分析
时间复杂度：O(n * sum(stones[i]))
空间复杂度：O(n * sum(stones[i]))

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(auto i:stones){
            sum+=i;
        }
        int bagweight=sum/2;
        vector<vector<int>> dp(stones.size()+1,vector<int> (bagweight+1));
        dp[0][0]=0;
        for(int i=1;i<=stones.size();i++){
            int weight=stones[i-1];
            for(int j=0;j<=bagweight;j++){
                if(weight>j){
                    dp[i][j]=dp[i-1][j];
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight]+weight);
                }
            }
        }
        return sum-dp[stones.size()][bagweight]-dp[stones.size()][bagweight];
    }
};

滚动数组优化
复杂度分析
时间复杂度：O(n * sum(stones[i]))
空间复杂度：O(sum(stones[i]))

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(auto i:stones){
            sum+=i;
        }
        int bagweight=sum/2;
        vector<int> dp(bagweight+1);
        for(int i=1;i<=stones.size();i++){
            int weight=stones[i-1];
            for(int j=bagweight;j>=weight;j--){
                dp[j]=max(dp[j],dp[j-weight]+weight);
            }
        }
        return sum-dp[bagweight]-dp[bagweight];
    }
};