LeetCode--1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II

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

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

• 如果 x == y，那么两块石头都会被完全粉碎；

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

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

---

我们需要从一堆石头里面选择两个石头来进行粉碎，得到的新石头是他们的差值，而我们需要返回最后可能的最小重量，我们可以将石头分为尽量均衡的两堆，假如两堆石头的所有石头都相互粉碎之后，得到的必然是另外几块石头，由于我们的差值都是以绝对值的形式出现，所以此时再将它分为两堆，这样不断分下去，此时得到的最小值必然是最开始两个石头的差值。

所以我们只需要考虑如何将两块石头尽量均匀即可，所以直接采取 01 背包，容量为 sum / 2 ：

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, x := range stones {
        sum += x
    }
    target := sum / 2
    f := make([]int, target + 1)
    for _, sto := range stones {
        for v := target; v >= sto; v -- {
            f[v] = max(f[v], f[v - sto] + sto)
        }
    }
    return sum - 2 * f[target]
}