Coin Change Minimum Coins in DSA Python

Mental Model

Find the smallest number of coins needed to make a target amount using given coin values. We build up solutions from smaller amounts to the target.

Analogy: Imagine you want to pay a certain amount using coins from your wallet. You try to pay small amounts first, remembering the fewest coins needed, then use that knowledge to pay bigger amounts efficiently.

coins: [1, 3, 4]
amount: 6

DP array (index = amount):
[0, ?, ?, ?, ?, ?, ?]
 ↑ start with 0 coins for amount 0

Dry Run Walkthrough

Input: coins: [1, 3, 4], amount: 6

Goal: Find the minimum number of coins needed to make amount 6

Step 1: Initialize dp array with 0 for amount 0 and infinity for others

dp: [0, ∞, ∞, ∞, ∞, ∞, ∞]

Why: We know 0 coins are needed to make amount 0; others unknown yet

Step 2: Calculate dp[1]: check coins 1,3,4; only coin 1 fits

dp: [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: To make amount 1, use coin 1 plus dp[0]=0 coins

Step 3: Calculate dp[2]: check coins 1,3,4; only coin 1 fits

dp: [0, 1, 2, ∞, ∞, ∞, ∞]

Why: To make amount 2, use coin 1 plus dp[1]=1 coin

Step 4: Calculate dp[3]: check coins 1,3,4; coins 1 and 3 fit

dp: [0, 1, 2, 1, ∞, ∞, ∞]

Why: Coin 3 fits exactly, so dp[3]=1 coin is better than dp[2]+1=3

Step 5: Calculate dp[4]: check coins 1,3,4; all fit

dp: [0, 1, 2, 1, 1, ∞, ∞]

Why: Coin 4 fits exactly, so dp[4]=1 coin

Step 6: Calculate dp[5]: check coins 1,3,4; all fit

dp: [0, 1, 2, 1, 1, 2, ∞]

Why: Best is coin 1 + dp[4]=1+1=2 coins

Step 7: Calculate dp[6]: check coins 1,3,4; all fit

dp: [0, 1, 2, 1, 1, 2, 2]

Why: Best is coin 3 + dp[3]=1+1=2 coins

Result:

dp: [0, 1, 2, 1, 1, 2, 2]
Minimum coins to make 6 is 2

Annotated Code

DSA Python

from math import inf

class CoinChange:
    def min_coins(self, coins, amount):
        dp = [0] + [inf] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], 1 + dp[a - c])
        return dp[amount] if dp[amount] != inf else -1

if __name__ == '__main__':
    coins = [1, 3, 4]
    amount = 6
    solver = CoinChange()
    result = solver.min_coins(coins, amount)
    print(result)

dp = [0] + [inf] * amount

Initialize dp array with 0 for amount 0 and infinity for others

for a in range(1, amount + 1):

Iterate over all amounts from 1 to target amount

for c in coins:

Try each coin to see if it fits in current amount

if c <= a:

Check if coin value is not bigger than current amount

dp[a] = min(dp[a], 1 + dp[a - c])

Update dp[a] with minimum coins using this coin

return dp[amount] if dp[amount] != inf else -1

Return minimum coins or -1 if amount cannot be formed

Output

2

Complexity Analysis

Time: O(n*m) because we compute dp for each amount (n) and try each coin (m)

Space: O(n) because we store minimum coins needed for each amount up to n

vs Alternative: Compared to recursive brute force exponential time, this dynamic programming approach is efficient and avoids repeated work

Edge Cases

amount is 0

Returns 0 because no coins are needed

DSA Python

dp = [0] + [inf] * amount

coins array empty

Returns -1 because no coins to form amount

DSA Python

return dp[amount] if dp[amount] != inf else -1

amount cannot be formed by given coins

Returns -1 indicating no solution

DSA Python

return dp[amount] if dp[amount] != inf else -1

When to Use This Pattern

When asked for the minimum number of items to reach a target sum using given denominations, use dynamic programming with a dp array to build solutions from smaller amounts.

Common Mistakes

Mistake: Not initializing dp array with infinity for amounts > 0
Fix: Initialize dp with dp = [0] + [inf] * amount to represent unknown minimums

Mistake: Not checking if coin value is less than or equal to current amount before using it
Fix: Add condition if c <= a before updating dp[a]

Mistake: Returning dp[amount] without checking if it is still infinity
Fix: Return -1 if dp[amount] is infinity to indicate no solution

Summary

Finds the minimum number of coins needed to make a target amount using given coin denominations.

Use when you need the least number of coins to form a specific amount from unlimited coins.

Build the solution from smaller amounts up to the target using a dp array that stores minimum coins needed.

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)