0

Given the dp array after running the bottom-up coin change minimum coins algorithm with coins = [1, 3, 4] and amount = 6: `dp = [0, 1, 2, 1, 1, 2, 2]` Which coin was used last to achieve dp[6] = 2?

hard🔄 Reverse Engineer Q9 of Q15

Dynamic Programming: Knapsack - Coin Change (Minimum Coins)

Given the dp array after running the bottom-up coin change minimum coins algorithm with coins = [1, 3, 4] and amount = 6: `dp = [0, 1, 2, 1, 1, 2, 2]` Which coin was used last to achieve dp[6] = 2?

ACoin 1

BCoin 3

CCoin 4

DImpossible to determine from dp array alone

Step-by-Step Solution

Solution:

Step 1: Check dp[6] = 2
dp[6] = min(1 + dp[6 - coin]) over coins.
Step 2: Test each coin
For coin 3: 1 + dp[3] = 1 + 1 = 2 matches dp[6]. For coin 4: 1 + dp[2] = 1 + 2 = 3 (no). For coin 1: 1 + dp[5] = 1 + 2 = 3 (no).
Final Answer:
Option B -> Option B
Quick Check:
Last coin used to get dp[6]=2 is coin 3 [OK]

Quick Trick: dp[i] = 1 + dp[i - last_coin] -> check which coin fits [OK]

Common Mistakes:

MISTAKES

Assuming largest coin always used
Ignoring dp values for subtractions

Trap Explanation:

PITFALL

Candidates guess largest coin or first coin without verifying dp consistency.

Interviewer Note:

CONTEXT

Tests ability to reverse engineer solution from dp array state.

Master "Coin Change (Minimum Coins)" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Dynamic Programming: Knapsack Quizzes