最后一块石头的重量 II

难度: Medium

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

提示：

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

Submission

运行时间: 21 ms

内存: 16.0 MB

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones) 
        odd = total & 1
        half = total // 2
        v = 1 << half
        for s in stones:
            v |= v >> s
        for i in range(half+1):
            if v & 1:
                return 2*i+odd
            v = v >> 1

Explain

此题可以转化为一个经典的动态规划问题。我们可以将问题理解为如何将石头分为两堆，使得这两堆石头的重量之差最小。这是一个类似于背包问题的变种，其中我们尝试找到总重量不超过总重量一半的最大重量。我们使用一个位向量来表示可以达到的重量，初始时只有重量0是可达的。对于每块石头，我们更新这个位向量，标记新的可达重量。最后，我们从最大可达重量开始向下检查，找到最接近总重量一半的值，这样可以保证两堆石头的重量差最小。

时间复杂度: O(n * total/2)

空间复杂度: O(total/2)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)  # 计算石头总重量
        odd = total & 1  # 检查总重量的奇偶性
        half = total // 2  # 计算总重量的一半
        v = 1 << half  # 初始化位向量，只有重量half可达
        for s in stones:
            v |= v >> s  # 更新位向量，标记通过当前石头可以达到的新重量
        for i in range(half+1):
            if v & 1:  # 从最接近half的位置开始检查
                return 2*i+odd  # 返回最小可能重量
            v = v >> 1  # 向右移位，减少检查的重量

Explore

原问题是将一组石头分成两堆，使得它们的重量差最小。这可以转化为寻找一种分配方式，使得一堆石头的重量尽可能接近总重量的一半。如果我们设总重量为sum，那么目标是使其中一堆的重量接近sum/2，这就形成了一个背包问题：从给定的石头中选取若干块，使得它们的总重量不超过sum/2的同时尽可能大。这是一个典型的0/1背包问题，因为每块石头只能选择或不选择（即0或1）。动态规划在这里适用，因为我们可以通过小问题的最优解构建大问题的最优解，即从已知小重量的最优组合推导出包含更多石头时的最优组合。

在动态规划解法中使用位向量`v`来表示达到某个重量是否可能。位向量的每个位代表一个重量，如果某位是1，则表示该重量可达。初始化时，只有重量0是可达的，因此位向量只在最低位为1。当加入一块石头重量`s`时，原有的可达重量集合通过向右移动`s`位来创建新的可达重量集合。这意味着，如果之前某个重量`w`可达（即`v`的第`w`位为1），那么加上这块石头后，重量`w+s`也将可达（即`v`的第`w+s`位也应设为1）。操作`v |= v >> s`是将原位向量向右移动`s`位，然后与原位向量进行逻辑或操作，从而更新位向量，使得所有通过添加当前石头能达到的新重量都被标记为可达。

位向量与常规的动态规划数组的主要区别在于空间效率。位向量通过每个二进制位来表示一个状态，因此相较于通常使用整数数组（其中每个数组元素通常占用至少4个字节）来存储状态的动态规划方法，位向量大大减少了内存占用。例如，一个常规的动态规划数组需要1000个整数来存储状态，则至少需要4000字节，而位向量只需要1000比特，大约125字节。此外，位向量的操作通常可以利用CPU的位操作指令，这可能在某些情况下提高运算效率。然而，位向量的缺点是它不如数组直观，且在某些情况下可能不容易处理更复杂的状态转移。