Coin Change Minimum Coins in DSA Python - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize dp array with large values

↓

Set dp[0

↓

For each coin

↓

For each sub-amount from coin to amount

↓

Update dp[sub-amount

↓

After all coins processed

↓

Check dp[amount

↓

If dp[amount

We build a dp array where each index represents the minimum coins needed for that amount. We update it by checking all coins for each sub-amount.

Execution Sample

DSA Python

coins = [1, 2, 5]
amount = 11
dp = [0] + [float('inf')] * amount
for coin in coins:
    for x in range(coin, amount + 1):
        dp[x] = min(dp[x], dp[x - coin] + 1)
print(dp[amount])

This code finds the minimum number of coins needed to make amount 11 using coins 1, 2, and 5.

Execution Table

Step	Operation	Sub-amount (x)	Coin Used	dp[x] Before	dp[x - coin]	dp[x] After	Visual dp Array Snapshot
1	Initialize dp	-	-	N/A	N/A	dp[0]=0, others=∞	[0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
2	coin=1, x=1	1	1	∞	dp[0]=0	1	[0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
3	coin=1, x=2	2	1	∞	dp[1]=1	2	[0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
4	coin=1, x=3	3	1	∞	dp[2]=2	3	[0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
5	coin=1, x=4	4	1	∞	dp[3]=3	4	[0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
6	coin=1, x=5	5	1	∞	dp[4]=4	5	[0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞]
7	coin=1, x=6	6	1	∞	dp[5]=5	6	[0, 1, 2, 3, 4, 5, 6, ∞, ∞, ∞, ∞, ∞]
8	coin=1, x=7	7	1	∞	dp[6]=6	7	[0, 1, 2, 3, 4, 5, 6, 7, ∞, ∞, ∞, ∞]
9	coin=1, x=8	8	1	∞	dp[7]=7	8	[0, 1, 2, 3, 4, 5, 6, 7, 8, ∞, ∞, ∞]
10	coin=1, x=9	9	1	∞	dp[8]=8	9	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ∞, ∞]
11	coin=1, x=10	10	1	∞	dp[9]=9	10	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ∞]
12	coin=1, x=11	11	1	∞	dp[10]=10	11	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
13	coin=2, x=2	2	2	2	dp[0]=0	1	[0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
14	coin=2, x=3	3	2	3	dp[1]=1	2	[0, 1, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11]
15	coin=2, x=4	4	2	4	dp[2]=1	2	[0, 1, 1, 2, 2, 5, 6, 7, 8, 9, 10, 11]
16	coin=2, x=5	5	2	5	dp[3]=2	3	[0, 1, 1, 2, 2, 3, 6, 7, 8, 9, 10, 11]
17	coin=2, x=6	6	2	6	dp[4]=2	3	[0, 1, 1, 2, 2, 3, 3, 7, 8, 9, 10, 11]
18	coin=2, x=7	7	2	7	dp[5]=3	4	[0, 1, 1, 2, 2, 3, 3, 4, 8, 9, 10, 11]
19	coin=2, x=8	8	2	8	dp[6]=3	4	[0, 1, 1, 2, 2, 3, 3, 4, 4, 9, 10, 11]
20	coin=2, x=9	9	2	9	dp[7]=4	5	[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 10, 11]
21	coin=2, x=10	10	2	10	dp[8]=4	5	[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 11]
22	coin=2, x=11	11	2	11	dp[9]=5	6	[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
23	coin=5, x=5	5	5	3	dp[0]=0	1	[0, 1, 1, 2, 2, 1, 3, 4, 4, 5, 5, 6]
24	coin=5, x=6	6	5	3	dp[1]=1	2	[0, 1, 1, 2, 2, 1, 2, 4, 4, 5, 5, 6]
25	coin=5, x=7	7	5	4	dp[2]=1	2	[0, 1, 1, 2, 2, 1, 2, 2, 4, 5, 5, 6]
26	coin=5, x=8	8	5	4	dp[3]=2	3	[0, 1, 1, 2, 2, 1, 2, 2, 3, 5, 5, 6]
27	coin=5, x=9	9	5	5	dp[4]=2	3	[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 5, 6]
28	coin=5, x=10	10	5	5	dp[5]=1	2	[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 6]
29	coin=5, x=11	11	5	6	dp[6]=2	3	[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
30	End	-	-	-	-	-	dp[11] = 3 (minimum coins)

💡 dp[11] = 3 means minimum 3 coins needed to make amount 11

Variable Tracker

Variable	Start	After coin=1	After coin=2	After coin=5	Final
dp	[0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]	[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]	[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]	[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

Key Moments - 3 Insights

Why do we initialize dp array with infinity except dp[0]?

dp[0] = 0 means zero coins needed for amount zero. Others start as infinity to represent unknown or impossible amounts. See execution_table step 1.

Why do we update dp[x] with dp[x - coin] + 1?

Because if we can make amount (x - coin) with dp[x - coin] coins, adding one coin (current coin) makes amount x. This is shown in execution_table steps 2-29.

Why does the final dp[amount] give minimum coins?

Because dp array is updated with minimum values at each step, so dp[amount] holds the smallest number of coins needed. See final step 30.

Visual Quiz - 3 Questions

Look at the execution_table at step 23, what is dp[5] after using coin 5?

A 3

B 1

C 5

D ∞

💡 Hint

Check the 'dp[x] After' column at step 23 for sub-amount 5.

At which step does dp[11] first get updated from infinity to a finite value?

A Step 29

B Step 22

C Step 12

D Step 30

💡 Hint

Look for the first step where dp[11] changes from ∞ to a number in the 'dp[x] After' column.

If we remove coin 1 from the coins list, how would dp[1] change after processing coin 2?

A dp[1] remains ∞

B dp[1] becomes 0

C dp[1] becomes 1

D dp[1] becomes 2

💡 Hint

Without coin 1, dp[1] cannot be formed by coin 2 or 5, so it stays ∞ as per the logic in execution_table steps for coin 2.

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array of size amount+1
- dp[0] = 0 (0 coins for amount 0)
- For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1)
- dp[amount] gives min coins or no solution if ∞
- Bottom-up dynamic programming approach

Full Transcript

This visualization shows how to find the minimum number of coins needed to make a given amount using dynamic programming. We start with a dp array initialized with infinity except dp[0] which is zero. For each coin, we update the dp array for all sub-amounts from the coin value up to the target amount. The dp[x] value is updated to the minimum between its current value and dp[x - coin] + 1, representing using one more coin. After processing all coins, dp[amount] holds the minimum coins needed or remains infinity if no combination is possible. The execution table traces each update step by step, showing how the dp array evolves. Key moments clarify why initialization is done with infinity, why dp updates use dp[x - coin] + 1, and why the final dp[amount] is the answer. The quiz tests understanding of dp updates and the effect of removing coins.

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?
coins = [1, 2, 5], amount = 11

easy

A. The minimum number of coins needed to make the amount

B. The maximum number of coins that can be used

C. The total sum of all coin values

D. The number of different coin types

Solution

1. Step 1: Understand the problem goal

   The problem asks for the fewest coins needed to sum up to the given amount using the available coin denominations.

2. Step 2: Clarify what is asked

   It is not about maximum coins or total sum, but the minimum count of coins to reach the amount.

3. Final Answer:

   The minimum number of coins needed to make the amount -> Option A

4. Quick Check:

   Minimum coins = goal [OK]

Hint: Focus on minimum coins to reach amount, not max or sum [OK]

Common Mistakes:

• Confusing minimum with maximum coins
• Thinking total sum of coins is the answer
• Counting coin types instead of coin count

2. Which of the following is the correct Python syntax to initialize a list dp of size amount + 1 with all values set to amount + 1?

easy

A. dp = [amount + 1] * amount

B. dp = [amount + 1 for i in range(amount)]

C. dp = [amount] * (amount + 1)

D. dp = [amount + 1] * (amount + 1)

Solution

1. Step 1: Understand list initialization

   We want a list of length amount + 1, each element set to amount + 1.

2. Step 2: Check each option

   dp = [amount + 1] * (amount + 1) correctly creates a list of length amount + 1 with all values amount + 1. dp = [amount + 1 for i in range(amount)] creates length amount, not amount + 1. dp = [amount + 1] * amount length is amount, not amount + 1. dp = [amount] * (amount + 1) sets values to amount, not amount + 1.

3. Final Answer:

   dp = [amount + 1] * (amount + 1) -> Option D

4. Quick Check:

   Correct list size and values [OK]

Hint: Use * operator with correct length for list initialization [OK]

Common Mistakes:

• Off-by-one error in list size
• Wrong value assigned to list elements
• Using list comprehension with wrong range

3. What is the output of the following code?

coins = [1, 3, 4]
amount = 6
dp = [7] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], dp[i - coin] + 1)
print(dp[amount])

medium

A. 6

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace dp array updates for amount=6

   Initialize dp = [0,7,7,7,7,7,7]. For i=1: dp[1]=min(7, dp[0]+1)=1. For i=2: dp[2]=min(7, dp[1]+1)=2. For i=3: dp[3]=min(7, dp[0]+1)=1. For i=4: dp[4]=min(7, dp[0]+1)=1. For i=5: dp[5]=min(7, dp[4]+1)=2. For i=6: dp[6]=min(7, dp[5]+1=3, dp[3]+1=2, dp[2]+1=3) so dp[6]=2.

2. Step 2: Final dp[6] value

   The minimum coins to make 6 is 2 (e.g., 3+3 or 4+1+1 but 2 coins is minimal).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array updates step-by-step for each amount [OK]

Common Mistakes:

• Not updating dp[i] correctly inside nested loops
• Confusing coin values with indices
• Forgetting to initialize dp[0] = 0

4. Find the error in the following code snippet for Coin Change Minimum Coins:

coins = [1, 2, 5]
amount = 11
dp = [amount + 1] * amount
dp[0] = 0
for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], dp[i - coin] + 1)
print(dp[amount])

medium

A. The inner loop should start from coin = 0

B. dp[0] should be set to amount + 1

C. dp list size is incorrect, should be amount + 1

D. The print statement should print dp[amount - 1]

Solution

1. Step 1: Check dp list initialization size

   dp is initialized with size amount, but indices go up to amount (11), so dp[11] access causes error.

2. Step 2: Correct dp size and consequences

   dp should be size amount + 1 to include index amount. dp[0] = 0 is correct. Other parts are fine.

3. Final Answer:

   dp list size is incorrect, should be amount + 1 -> Option C

4. Quick Check:

   dp size = amount + 1 [OK]

Hint: dp size must cover all indices up to amount [OK]

Common Mistakes:

• Off-by-one error in dp list size
• Incorrect initialization of dp[0]
• Wrong index in print statement

5. Given coins = [2, 5] and amount = 7, which of the following code snippets correctly returns the minimum number of coins needed or -1 if not possible?

hard

A. def min_coins(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != amount + 1 else -1

B. def min_coins(coins, amount):
dp = [0] * (amount + 1)
for i in range(1, amount + 1):
dp[i] = min(dp[i - coin] + 1 for coin in coins if coin <= i)
return dp[amount]

C. def min_coins(coins, amount):
dp = [float('inf')] * amount
dp[0] = 0
for i in range(1, amount):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount - 1]

D. def min_coins(coins, amount):
dp = [amount] * (amount + 1)
dp[0] = 1
for i in range(1, amount + 1):
for coin in coins:
if coin < i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount]

Solution

1. Step 1: Analyze each code snippet

   def min_coins(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1 correctly initializes dp with amount + 1 size and value, sets dp[0]=0, updates dp[i] properly, and returns -1 if no solution. def min_coins(coins, amount): dp = [0] * (amount + 1) for i in range(1, amount + 1): dp[i] = min(dp[i - coin] + 1 for coin in coins if coin <= i) return dp[amount] lacks initialization for dp[0] and may cause error if no valid coins. def min_coins(coins, amount): dp = [float('inf')] * amount dp[0] = 0 for i in range(1, amount): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount - 1] uses wrong dp size and indices, and returns dp[amount - 1] incorrectly. def min_coins(coins, amount): dp = [amount] * (amount + 1) dp[0] = 1 for i in range(1, amount + 1): for coin in coins: if coin < i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] sets dp[0]=1 incorrectly and uses wrong coin comparison (coin < i instead of coin <= i).

2. Step 2: Confirm correctness of def min_coins(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1

   def min_coins(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1 matches the standard dynamic programming solution for minimum coins with proper edge case handling.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Standard DP solution with correct initialization and return [OK]

Hint: Check dp size, dp[0], coin comparison, and return condition [OK]

Common Mistakes:

• Wrong dp list size or initialization
• Incorrect dp[0] value
• Using coin < i instead of coin <= i
• Not handling no solution case (-1)