Dynamic Programming: Knapsack - Last Stone Weight II
Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
easy🧾 Code Trace Q12 of Q15
Step-by-Step Solution
Step 1: Calculate total and half
Total = 6, half = 3. dp array size = 4, dp[0] = true initially.Step 2: Update dp for each stone
For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.Step 3: Find largest w ≤ half with dp[w] = true
dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.Final Answer:
Option B -> Option BQuick Check:
Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Quick Trick: Check dp array for sums up to half total [OK]
Common Mistakes:
MISTAKES- Returning total instead of minimal difference
- Off-by-one error in dp indexing
- Not iterating backwards in dp update
Trap Explanation:
PITFALL- Candidates often confuse dp indexing or final sum calculation, leading to off-by-one or wrong difference.
Interviewer Note:
CONTEXT- Tests ability to trace DP updates and final result calculation.
Master "Last Stone Weight II" in Dynamic Programming: Knapsack
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Dynamic Programming: Knapsack Quizzes