NeetCode #719LC-1049Medium2-D Dynamic ProgrammingNC 250
← Back to All Problems#719 · #1049 · Last Stone Weight II(最后一块石头的重量 II)
📌 Problem Statement & Constraints
Given stone weights
stones, repeatedly smash two stones together: if they are equal both vanish, otherwise the larger becomes their difference. Return the smallest possible weight of the last remaining stone. Constraints: 1 <= stones.length <= 30, 1 <= stones[i] <= 100, so sum(stones) <= 3000.💡 Core Algorithmic Approaches
- The process is equivalent to partitioning the stones into two groups whose weight difference is minimised.
- Let
total = sum(stones); we want a subset sum as close tototal / 2as possible. - Run a 0/1 knapsack boolean DP over achievable subset sums up to
total // 2. - The answer is
total - 2 * best, wherebestis the largest achievable sum not exceedingtotal // 2.
💻 Benchmark Python3 Implementation
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
half = total // 2
dp = [False] * (half + 1)
dp[0] = True
for w in stones: # 0/1 knapsack: descending sums
for s in range(half, w - 1, -1):
dp[s] = dp[s] or dp[s - w]
for s in range(half, -1, -1):
if dp[s]:
return total - 2 * s
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * total): each stone is offered to every reachable sum.
💾 Space Complexity
O(total): the boolean DP array.
⚠️ Interview Pitfalls & Follow-ups
- Using ascending sums: that reuses a stone, turning it into an unbounded knapsack.
- Answering with
total - best: the two groups' difference istotal - 2 * best. - Searching the full sum range: only sums up to
total // 2matter, since the two groups are symmetric. - Simulating the smashing literally: the partition view is equivalent and far simpler.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.