Coin Change (LeetCode 322)

The problem

You get a list of coin denominations coins (unlimited supply of each) and a target amount. Return the fewest coins that add up to exactly amount, or -1 if it can’t be done.

Input:  coins = [1, 2, 5], amount = 11
Output: 3

5 + 5 + 1 = 11 uses three coins, and no two coins reach 11.

How to think about it

Start with greedy, then brute force. Taking the largest coin first works for [1, 2, 5] but fails in general: with coins [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 (3 coins) while 3 + 3 uses 2. Brute force recursion tries every coin at every step, which is exponential because the same remaining amounts come up again and again.

The key insight: think about the last coin. Whatever the best way to make a is, it ends with some coin c. Remove it and what’s left is the best way to make a - c. So dp[a] = min over coins c ≤ a of dp[a - c] + 1, with dp[0] = 0.

Fill the table bottom-up. Every dp[a] depends only on smaller amounts, so compute dp[1], dp[2], …, dp[amount] in order. Unreachable amounts stay at infinity, which also means “impossible” propagates naturally: infinity plus one is still infinity.

Which pattern is this? 1-D DP, specifically unbounded knapsack (each coin can be reused). The tell is “minimum number of items to reach a total” where greedy breaks.

Approach

1. Make dp of size amount + 1: dp[0] = 0, everything else infinity.
2. For each amount a from 1 to amount, for each coin c that fits (c <= a): set dp[a] = min(dp[a], dp[a - c] + 1).
3. Return dp[amount], or -1 if it is still infinity.

Solution

def coin_change(coins, amount):
    INF = float("inf"); dp = [0] + [INF] * amount     # dp[a] = fewest coins for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)   # last coin is c
    return -1 if dp[amount] == INF else dp[amount]
# coin_change([1,2,5], 11) -> 3  (5 + 5 + 1)

Dry run

For coins = [1, 2, 5], the final table is dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]. A few entries in detail:

So dp[11] = 3.

Complexity

• Time: O(amount · len(coins)). Each amount tries each coin once.
• Space: O(amount). The dp array.

Edge cases and pitfalls

• amount = 0 returns 0 (no coins needed).
• Impossible amounts (coins = [2], amount = 3) return -1; forgetting the infinity check returns inf.
• Greedy largest-coin-first is the most common wrong answer; have a counter-example like [1, 3, 4], 6 ready.
• Using amount + 1 as infinity also works and keeps everything an integer.

Related problems

• Coin Change II (LeetCode 518): count the combinations instead of the minimum; loop order starts to matter.
• Partition Equal Subset Sum (LeetCode 416): the 0/1 knapsack cousin, where each number is used at most once.
• Word Break (LeetCode 139): the same “try every last piece” recurrence over a string.