⚡Flashcard Drill➔
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

  1. The process is equivalent to partitioning the stones into two groups whose weight difference is minimised.
  2. Let total = sum(stones); we want a subset sum as close to total / 2 as possible.
  3. Run a 0/1 knapsack boolean DP over achievable subset sums up to total // 2.
  4. The answer is total - 2 * best, where best is the largest achievable sum not exceeding total // 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 is total - 2 * best.
  • Searching the full sum range: only sums up to total // 2 matter, 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems