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

解题思路

这道题的关键洞察是将问题转化为分割数组为两个子集，使得两个子集的差值最小。

思路分析

当我们不断地粉碎石头时，实际上是在给每个石头分配正号或负号。最终的结果就是所有石头重量的加权和，其中权重为 +1 或 -1。

设总重量为 sum，我们要将石头分为两组：

  • 第一组重量为 S1，权重为正
  • 第二组重量为 S2 = sum - S1，权重为负

最终结果为 S1 - S2 = S1 - (sum - S1) = 2*S1 - sum

要使结果最小，我们需要让 S1 尽可能接近 sum/2，但不能超过。

动态规划解法

这转化为经典的背包问题：在容量为 sum/2 的背包中，选择石头使得总重量尽可能大。

状态定义：dp[i] 表示是否能够凑出重量 i

状态转移：对于每个石头 stone，更新 dp[i] = dp[i] || dp[i-stone]（从大到小遍历避免重复使用）

最终答案：找到最大的可达到重量 j ≤ sum/2，答案为 sum - 2*j

推荐解法：动态规划背包问题，时间复杂度 O(n×sum)，空间复杂度 O(sum)。

代码实现

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        
        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
        
        return 0;
    }
};

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total_sum = sum(stones)
        target = total_sum // 2
        
        dp = [False] * (target + 1)
        dp[0] = True
        
        for stone in stones:
            for j in range(target, stone - 1, -1):
                dp[j] = dp[j] or dp[j - stone]
        
        for j in range(target, -1, -1):
            if dp[j]:
                return total_sum - 2 * j
        
        return 0

public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int sum = stones.Sum();
        int target = sum / 2;
        
        bool[] dp = new bool[target + 1];
        dp[0] = true;
        
        foreach (int stone in stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        
        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
        
        return 0;
    }
}

var lastStoneWeightII = function(stones) {
    const sum = stones.reduce((acc, stone) => acc + stone, 0);
    const target = Math.floor(sum / 2);
    
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    
    for (const stone of stones) {
        for (let j = target; j >= stone; j--) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }
    
    for (let j = target; j >= 0; j--) {
        if (dp[j]) {
            return sum - 2 * j;
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × sum)n为石头数量，sum为所有石头重量之和
空间复杂度O(sum)动态规划数组的大小

相关题目