Dynamic Programming: Knapsack - Last Stone Weight II
What is the output of the space-optimized lastStoneWeightII function when stones = [10]?
What is the output of the space-optimized lastStoneWeightII function when stones = [10]?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: Calculate total and half
Total=10, half=5Step 2: Update dp array
Weight=10 > half=5, so inner loop does not run; dp remains dp[0]=True onlyStep 3: Find max w ≤ half with dp[w]=True
Only w=0 is True, so return 10 - 2*0 = 10Final Answer:
Option C -> Option CQuick Check:
Single stone cannot be split -> difference equals stone weight [OK]
Quick Trick: Single stone weight > half -> difference equals total [OK]
Common Mistakes:
MISTAKES- Expecting dp update for weight > half
- Off-by-one in loop bounds
- Assuming error on single element
Trap Explanation:
PITFALL- Candidates expect dp update even when weight > half, but loop skips, returning total.
Interviewer Note:
CONTEXT- Checks handling of edge cases and loop boundary correctness
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