LeetCode 1049：最后一块石头的重量 II —— 题解 ✅

乄卝⑦

345人浏览 · 2026-06-05 14:29:53

乄卝⑦ · 2026-06-05 14:29:53 发布

LeetCode 1049：最后一块石头的重量 II —— 题解 ✅

🔗 题目链接

👉 https://leetcode.cn/problems/last-stone-weight-ii/

📖 内容概要

有一堆石头，每块石头的重量为 stones[i]。
每次任选两块石头 x 和 y，将它们一起粉碎，剩余重量为 |x - y|。
求最后剩下石头的 最小可能重量。

✅ 0/1 背包
✅ 分割等和子集的变形
✅ 面试高频 / medium思维题

💡 解题思路（核心）

一、关键转化（非常重要）

最终剩余重量最小 ⇔ 把石头分成两堆，使两堆总重量尽可能接近

因为：

最终重量 = |sumA - sumB|

当 sumA ≈ sumB 时，结果最小。

二、问题等价于

从数组中选取若干石头，使其总和不超过 sum / 2，且尽可能大

👉 典型的 0/1 背包问题

三、DP 定义

dp[j] = 容量为 j 的背包，能装的最大重量

目标：

max(dp[target])

四、状态转移方程

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

✅ 每个石头只能用一次
✅ 必须 倒序遍历

五、最终答案

sum - dp[target] - dp[target]
= sum - 2 × dp[target]

✅ AC 代码（Java）

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

        int target = sum / 2;
        int[] dp = new int[1505];

        // 0/1 背包
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(
                    dp[j],
                    dp[j - stones[i]] + stones[i]
                );
            }
        }

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