• 1 ≤ coins.length ≤ 12
• 1 ≤ coins[i] ≤ 2³¹ - 1
• 0 ≤ amount ≤ 10⁴
• Each denomination may be used any number of times

You have coins of a few fixed values, with an unlimited number of each. Pay an exact amount using as few coins as possible. If you cannot pay it exactly, return -1.

Two things shape the solution:

Coins are unlimited. You can use the same value again and again. So a choice is never "use this coin or lose it forever" — after using a coin you may use it again.

We want the fewest coins. So when we compare choices, we keep the smallest count. And we need a way to say "this amount cannot be paid at all", because some amounts truly cannot be.

The obvious approach: repeatedly take the largest coin that still fits. With the coins in your pocket right now — 1, 2, 5, 10, 20, 50 — that rule always gives the fewest coins, which is why it feels like a law of nature. It is not. It is a property of the particular denominations, carefully chosen by mints so that cashiers can work quickly.

Break it with coins = [1, 3, 4], amount = 6. Greedy takes 4, leaving 2, then takes 1 and 1 — three coins. But 3 + 3 is two coins. The big coin looked efficient and left behind a remainder that only awkward coins could fill.

There is no fix by reordering or tie-breaking. When a locally best choice can poison the remainder, you must compare the futures of all the choices, and that is what the recurrence does.

Say I still owe amount a. I pick one coin c that fits (c <= a), pay it, and now I owe a - c — the same kind of problem, just smaller. Since coins are unlimited, the only thing I need to track is how much I still owe. That single number is the state.

I don't know which coin to place, so I try every coin that fits, add 1 for the coin I placed, and keep the smallest:

f(a) = 1 + min over every coin c with c <= a of f(a - c)

The min picks the fewest coins; the 1 counts the coin I just placed.

Base case: f(0) = 0 — paying nothing needs no coins. If no coin fits, f(a) stays infinity, which means "cannot be made".

def coin_change(coins, amount):
    INF = float('inf')

    def f(a):
        if a == 0: return 0
        best = INF
        for c in coins:
            if c <= a:
                sub = f(a - c)
                if sub + 1 < best:
                    best = sub + 1
        return best

    result = f(amount)
    return -1 if result == INF else result

Each call branches into up to len(coins) more, so the raw tree is huge. But there are only amount + 1 different questions — f(0) through f(amount). So keep a notebook: compute each once, then reuse it:

def coin_change(coins, amount):
    INF = float('inf')
    memo = {}

    def f(a):
        if a == 0: return 0
        if a in memo: return memo[a]
        best = INF
        for c in coins:
            if c <= a:
                best = min(best, 1 + f(a - c))
        memo[a] = best
        return best

    result = f(amount)
    return -1 if result == INF else result

amount + 1 states, each looping over len(coins) denominations: O(amount × coins) time.

Now turn it into a table. Let dp[a] hold what f(a) returned. The recurrence becomes the same line with array reads: dp[a] = 1 + min over each coin c <= a of dp[a - c]. Since dp[a] needs smaller amounts, fill from a = 0 upward, so every value it needs is ready when you reach it. The base case copies over: dp[0] = 0:

def coin_change(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] != INF:
                dp[a] = min(dp[a], dp[a - c] + 1)

    return -1 if dp[amount] == INF else dp[amount]

Because the only state is the amount, this table is already a single array of size amount + 1. There is no bigger table to shrink, so O(amount) space is where we stop.

We sweep amounts upward, and reusing a coin is fine — in fact it is what we want, since coins are unlimited. When we read dp[a - c], it may already have used coin c, and that is correct here.

The order is also safe because we take a minimum. "What is the fewest coins" gives the same answer no matter which order we try the coins in, so nothing is double-counted. (Counting the number of ways is fussier about order, but that is a different question.)

Answer 2 — the 3 + 3 that greedy could not see. Note how dp[3] = 1 was computed once and then reused, which is the whole point of the table.

Now an impossible case, coins = [5], amount = 3: no coin ever fits, dp[3] stays infinite, and we return -1.

Three habits to keep from this page.

When a greedy rule is proposed, try to break it before you trust it. One counterexample settles the question permanently, and finding it takes thirty seconds: look for a case where the big obvious choice leaves an awkward remainder.

Ask what the future really depends on, and put only that in the state. Here it was a single number, because the coins never run out. If each coin could be used only once, the state would also need to track which coins are left. The state is not a formula to memorise — it follows from the rules.

Have a plan for "impossible". When some inputs have no answer, use a sentinel — infinity, or amount + 1 — that a real answer can never equal, and make sure arithmetic on it never leaks back into the table as a real-looking number.