【Leetcode】1049. Last Stone Weight II（配数学证明）

题目地址：

https://leetcode.com/problems/last-stone-weight-ii/description/

给定$n$个石头的重量数组$A$，允许每次将两个石头相碰，得重量为两个石头的重量之差的小石头（如果碰的两个石头重量相等，则两个石头都消失）。问最后能得到的重量最小的石头的重量。

首先，最后一个石头的重量的表达式必然为$A$中数每个数前面加上或者正号或者负号，最后求和而得。假设最优解对应的赋正负号的方式已经知道，我们证明，一般的对于$A$的正负号的赋予方式（即不管具体石头碰撞能不能实现这种赋予方式）所得的总和最小值一定存在某个碰石头的方案。这样求碰石头这一具体范围的最优解等价于在一个更大的范围上求最优解。

证明如下：将最优解取出来，将所有赋予正号的数放入集合$A$，剩余数放入集合$B$（当然这里的集合是多重集合，不是数学里的那个集合），我们找到这两个集合的最大值，比如其是$x\in A$，随便取一个数$y\in B$，则$y\le x$，我们将$x$替换为$x-y$，$B$中的$y$删掉，那么效果就是总共的数字个数少了$1$（或$2$）个。如此这般下去，可以证明最后一定只剩下一个数，否则的话还可以继续做一次碰撞得到更小的石头（因为$\forall x,y,|x-y|<x+y$），这就说明最优解一定是某个碰石头的方案。

而求更大范围的最优解，实际上就是求将$A$划分为两部分$S_1,S_2$使得$0\le \sum S_1-\sum S_2=\sum A-2\sum S_2$最小，也就是求小于等于$(\sum A)/2$的最大$\sum S_2$，这是个$01$背包问题，可以动态规划。代码如下：

class Solution {
 public:
  int lastStoneWeightII(vector<int>& ss) {
    int sum = 0, n = ss.size();
    for (auto x : ss) sum += x;
    int f[sum / 2 + 1];
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; i++)
      for (int j = sum / 2; j >= ss[i - 1]; j--)
        f[j] = max(f[j], f[j - ss[i - 1]] + ss[i - 1]);

    return sum - 2 * f[sum / 2];
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度$O(n\sum A)$，空间$O(\sum A)$。