Bird
Raised Fist0

Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?

easy🧾 Code Trace Q12 of Q15
Dynamic Programming: Knapsack - Coin Change (Minimum Coins)
Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount]

print(coinChange([1,2,5], 5))
A5
B2
C3
D1
Step-by-Step Solution
Solution:
  1. Step 1: Trace dp array updates up to i=5

    dp[0]=0; For i=1: dp[1]=min(inf,1+dp[0])=1; i=2: dp[2]=min(inf,1+dp[1],1+dp[0])=1; i=3: dp[3]=min(inf,1+dp[2],1+dp[1])=2; i=4: dp[4]=min(inf,1+dp[3],1+dp[2])=2; i=5: dp[5]=min(inf,1+dp[4],1+dp[3],1+dp[0])=min(inf,3,3,1)=1
  2. Step 2: Confirm dp[5] value

    Using coin 5 directly gives dp[5]=1, which is minimal.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    dp[5] = 1 coin (coin 5) [OK]
Quick Trick: Direct coin equal to amount sets dp[amount] to 1 [OK]
Common Mistakes:
MISTAKES
  • Off-by-one errors in indexing dp
  • Ignoring direct coin match
Trap Explanation:
PITFALL
  • Candidates often forget dp[0]=0 base case or miscalculate dp[i] updates leading to wrong dp[5].
Interviewer Note:
CONTEXT
  • Checks candidate's ability to mentally execute DP code and handle base cases correctly.
Master "Coin Change (Minimum Coins)" 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