Bird
Raised Fist0

Given the function below, what is the output when stones = [2, 7, 4]?

easy🧾 Trace Q3 of Q15
Dynamic Programming: Knapsack - Last Stone Weight II
Given the function below, what is the output when stones = [2, 7, 4]? ```python def lastStoneWeightII(stones): total = sum(stones) half = total // 2 dp = [False] * (half + 1) dp[0] = True for stone in stones: for j in range(half, stone - 1, -1): dp[j] = dp[j] or dp[j - stone] for j in range(half, -1, -1): if dp[j]: return total - 2 * j ```
A5
B3
C1
D7
Step-by-Step Solution
Solution:
  1. Step 1: Calculate total sum

    2 + 7 + 4 = 13, half = 6
  2. Step 2: Determine reachable sums up to 6

    Possible sums up to 6 are 0,2,4,6 (2+4). 7 and above exceed half and are not considered.
  3. Step 3: Find largest j ≤ 6 where dp[j] is True

    j = 6 is reachable (2+4)
  4. Final Answer:

    13 - 2*6 = 1 -> Option C
  5. Quick Check:

    Minimal difference is 1 [OK]
Quick Trick: Find largest subset sum ≤ half total sum [OK]
Common Mistakes:
MISTAKES
  • Not initializing dp[0] to True
  • Iterating dp forward instead of backward
  • Miscomputing total sum or half
Trap Explanation:
PITFALL
  • Incorrect dp initialization or iteration order leads to wrong reachable sums.
Interviewer Note:
CONTEXT
  • Tests ability to trace DP code and understand subset sum logic.
Master "Last Stone Weight II" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Dynamic Programming: Knapsack Quizzes