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

标签：数组、动态规划
难度：中等

题目大意 #

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

每一回合，从石头中选出任意两块石头，将这两块石头一起粉碎。假设石头的重量分别为 x 和 y。且 x ≤ y，则结果如下：

如果 x == y，则两块石头都会被完全粉碎；
如果 x < y，则重量为 x 的石头被完全粉碎，而重量为 y 的石头新重量为 y - x。

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

解题思路 #

选取两块石头，重新放回去的重量是两块石头的差值绝对值。重新放回去的石头还会进行选取，然后进行粉碎，直到最后只剩一块或者不剩石头。

这个问题其实可以转化为：把一堆石头尽量平均的分成两对，求两堆石头重量差的最小值。

这就和「 0416. 分割等和子集」有点相似。两堆石头的重量要尽可能的接近数组总数量和的一半。

进一步可以变为：假设石头总重量和为 sum，则问题为将一堆石头放进容量最多为 sum / 2 的背包中，获得的最大价值为 max_weight（即其中一堆石子的重量），则另一堆石子的重量为 sum - max_weight。则两者的差值为 sum - 2 * max_weight，即为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        size = 15010
        dp = [0 for _ in range(size)]
        sum_stones = sum(stones)
        target = sum_stones // 2
        for i in range(len(stones)):
            for j in range(target, stones[i]-1, -1):
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

        return sum_stones - dp[target] * 2