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

Categories:

题目描述
思路分析
1. 解法一：0/1 背包（推荐）
相似题目

题目描述

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

思路分析

解法一：0/1 背包（推荐）

核心思路：

将石头分成两堆，问题等价于让两堆重量差最小。

设总和为 S，目标是在不超过 S/2 的情况下尽量接近。

用 0/1 背包求最大可达重量 best，答案为 S - 2 * best。

复杂度分析：

时间复杂度：O(n · S)，其中 n 表示石头数量，S 表示总重量的一半。

空间复杂度：O(S)。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int s : stones) {
            sum += s;
        }

        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int w : stones) {
            for (int j = target; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + w);
            }
        }

        return sum - 2 * dp[target];
    }
}

func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, s := range stones {
		sum += s
	}

	target := sum / 2
	dp := make([]int, target+1)

	for _, w := range stones {
		for j := target; j >= w; j-- {
			if dp[j-w]+w > dp[j] {
				dp[j] = dp[j-w] + w
			}
		}
	}

	return sum - 2*dp[target]
}

相似题目

题目	难度	考察点
1049. 最后一块石头的重量 II	中等	0/1 背包
416. 分割等和子集	中等	0/1 背包
494. 目标和	中等	0/1 背包
879. 盈利计划	困难	0/1 背包
474. 一和零	中等	0/1 背包
322. 零钱兑换	中等	完全背包

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/90090811