Coin Change 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #322: Coin Change — the classic DP problem! 🪙

💡 Think of it like this: You're at a vending machine that only takes certain coin types. You need to make exact change for a certain amount. What's the fewest coins you need?

# Example:
coins = [1, 5, 10, 25]  # penny, nickel, dime, quarter
amount = 30
# Answer: 2 coins (25 + 5)
# Not 3 coins (10 + 10 + 10)
# Not 6 coins (5 + 5 + 5 + 5 + 5 + 5)

The DP Approach: Build up from amount 0 to the target amount. For each amount, try every coin and pick the one that gives the fewest total coins.

Recurrence: dp[amount] = min(dp[amount - coin] + 1) for each valid coin

💭 Go for it! Apply the approach above in your own code. If you get stuck, use the hint below! 🔥

Step-by-step for coins=[1,3,4], amount=6:

dp[0] = 0 (base case)
dp[1] = dp[0]+1 = 1 (use coin 1)
dp[2] = dp[1]+1 = 2 (use coin 1)
dp[3] = min(dp[2]+1, dp[0]+1) = 1 (use coin 3!)
dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1 (use coin 4!)
dp[5] = min(dp[4]+1, dp[2]+1) = 2
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2 (coins 3+3) ✓

Complexity: Time O(amount × len(coins)), Space O(amount).

📋 Instructions

Find minimum coins for amount 11 with coins [1,5,6].

Create dp array where dp[i] = fewest coins for amount i. For each amount, try every coin: dp[amount] = min(dp[amount], dp[amount-coin] + 1). Base: dp[0] = 0.

⚠️ Try solving it yourself first — you'll learn more!

def coinChange(coins, amount):
    # dp[i] = fewest coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins needed to make amount 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:  # Can we use this coin?
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

🧪 Test Cases

Input

coinChange([1, 5, 6], 11)

Expected

2

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›