华为 OD 训练营 · 题解精讲

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

题目描述

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

题目解析

解题思路

本题的实质是将石头分成两堆，使得两堆重量差最小。每次粉碎操作相当于从两堆中各取一块石头，较大者减去较小者后放回，最终剩下的石头就是两堆重量之差的绝对值。因此问题转化为：从所有石头中选出一部分，使其总重量尽可能接近总重量的一半（不超过一半），这样两堆的差值最小。

这是一个0-1背包问题：每个石头重量既是物品重量也是物品价值，背包容量为 total // 2，目标是求不超过背包容量的最大重量和。

关键步骤

1. 计算石头总重量 total，目标容量 target = total // 2。 2. 初始化二维 DP 数组 dp[i][j]，表示前 i 个石头中选出总重量不超过 j 的最大重量。 3. 遍历每个石头（索引 i 从 1 到 n）：

若当前石头重量 stones[i-1] 大于背包容量 j，则不能选：dp[i][j] = dp[i-1][j]
否则，取“不选”和“选”的最大值：


     dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1])

4. 最终 dp[n][target] 是一堆的最大重量，另一堆重量为 total - dp[n][target]，两堆差值为 total - 2 * dp[n][target]。

复杂度分析

时间复杂度：O(n × target)，其中 n 为石头个数，target ≤ total/2 ≤ 1500（石头最大总重 30×100=3000），实际计算量约 30×1500 = 45000。
空间复杂度：O(n × target)（二维数组）或 O(target)（滚动数组优化）。

参考代码

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        # 因此可以将数组分成 A 和 B 两个部分
        # A 部分的石头可以被部分留下
        # B 部分的石头全部被粉碎

        # 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        # 其中 A 部分的石头重量和是 sumA
        # 其中 B 部分的石头重量和是 sumB
        # 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        # 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        # 先去计算总和
        total = sum(stones)

        target = total // 2

        # dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
        dp = [[0] * (target + 1) for _ in range(len(stones) + 1)]

        # 01 背包问题开始填充二维数组
        for i in range( 1 , len(stones) + 1 ) :

            for j in range( target + 1):
            

                # 注意到 i 是从下标 1 开始访问的
                # 1、背包容量小于当前元素
                # 背包无法放入 stones[i - 1]
                if  j < stones[i - 1] :

                    dp[i][j] = dp[ i - 1 ][j]

                # 2、背包容量大于等于当前元素
                # 背包可以放入 stones[i - 1]
                else:

                    # 不选：方案数为 dp[i - 1][j]
                    # 选：方案数为 dp[i - 1][j - stones[i - 1]] + stones[i-1]
                    dp[i][j] = max(dp[i-1][j] , dp[i-1][j - stones[i-1]] + stones[i-1])
   
       
        # 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
        return total - 2*dp[len(stones)][target] 

# 滚动数组
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
        # 因此可以将数组分成 A 和 B 两个部分
        # A 部分的石头可以被部分留下
        # B 部分的石头全部被粉碎

        # 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
        # 其中 A 部分的石头重量和是 sumA
        # 其中 B 部分的石头重量和是 sumB
        # 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
        # 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

        # 先计算总和
        sum = 0
        for num in stones:
            sum += num

        target = sum // 2

        # dp[i] 代表考虑前 i 个物品（数值），凑成总和不超过 target 的最大价值
        dp = [0] * (target + 1)

        # 01 背包问题开始填充一维数组
        for i in range(1, len(stones) + 1):
            for j in range(target, -1, -1):
                # 注意到 i 是从下标 1 开始访问的
                if j >= stones[i - 1]:
                    dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1])

        # 这两个部分最大值是 dp[len(stones)][target]，剩余的部分就是剩下的石头
        return abs(sum - dp[target] - dp[target])

← 上一篇

LC1047. 删除字符串中的所有相邻重复项

LC1052. 爱生气的书店老板