LeetCode 1049: Last Stone Weight II ·

基本資料
#

難易度: medium 第一次嘗試：2026-08-19 來源：Day 45 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

explain LC 1049 as a partition problem, not a simulation problem

當天筆記摘錄
#

Problem 2 - LC 1049 Last Stone Weight II
#

Pattern: 0/1 subset partition with best-half approximation.

Why This Fits
#

If the stones are partitioned into two groups with sums:

A and B

then the final remaining weight is:

|A - B|

So the real goal is:

find a reachable subset sum as close as possible to total / 2

Core State / Invariant
#

dp[s] = whether some subset of processed stones can make sum s

Base Case
#

dp[0] = true

Reason:

choosing no stones makes sum 0

Transition
#

For each stone, iterate backward:

dp[s] |= dp[s - stone]

Final Answer
#

Find the largest reachable:

s <= total // 2

Then return:

total - 2 * s

Complexity
#

Time: O(len(stones) * target)
Space: O(target)

Common Mistakes
#

treating smash operations as simulation instead of partitioning
using forward iteration and reusing one stone
thinking maximize-value DP is required
forgetting the final scan for best reachable half

Strong Spoken Explanation
#

I reframe the smash process as partitioning stones into two groups. If the group sums are A and B, the final leftover is |A - B|, so I want the two sums as close as possible. That means I only need subset sums up to total // 2. I use boolean 0/1 DP where dp[s] tells me whether sum s is reachable from the processed stones. After filling the table, I scan downward from total // 2 for the largest reachable s and return total - 2 * s.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for stone in stones:
            for s in range(target, stone - 1, -1):
                dp[s] = dp[s] or dp[s - stone]

        for s in range(target, -1, -1):
            if dp[s]:
                return total - 2 * s
        return 0