Coin Change

Problem Statement

Given coin denominations and a target amount, return the fewest coins needed to make that amount. You have an unlimited supply of each coin. If the amount cannot be made, return -1.

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

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

Input:  coins = [1], amount = 0
Output: 0

Intuition

The instinct is to take the largest coin that fits, repeatedly. With real currency that works, which is exactly why it is such a dangerous habit.

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

Greedy: take 4  →  remaining 2
        take 1  →  remaining 1
        take 1  →  remaining 0
        Total: 3 coins  (4 + 1 + 1)

Best:   3 + 3  =  2 coins

Since no local rule can be trusted, every option has to be considered.

fewest(a) = 1 + min( fewest(a - c) for every coin c that fits )

Because fewest(a - c) is reused by many different a, this is dynamic programming rather than plain recursion.

Building from the bottom

Rather than recursing down from amount, build up from 0. To make 0 you need 0 coins — that is the anchor. Every later answer leans on earlier ones that are already final.

coins = [1, 2, 5]

amount:  0   1   2   3   4   5   6  ...
fewest:  0   1   1   2   2   1   2  ...
                     ↑
              3 = 2 + 1  →  1 + fewest(1) = 2

The real-world version

You are working out the fewest notes to pay a bill, and you have a notebook where you have already recorded the answer for every smaller amount.

For £11 you check each note you own: "if my last note is a £5, I still owe £6 — and I already know £6 takes 2 notes, so that path is 3." Do that for every note and keep the smallest.

Approach

Watch it run

Solution

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins summing to amount, or -1 if impossible."""
    # amount + 1 is larger than any real answer, so it doubles as "impossible".
    IMPOSSIBLE = amount + 1
    fewest = [IMPOSSIBLE] * (amount + 1)

    # Anchor: making 0 needs 0 coins.
    fewest[0] = 0

    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value:
                # Use this coin as the last one, then reuse a solved subproblem.
                fewest[value] = min(fewest[value], 1 + fewest[value - coin])

    return fewest[amount] if fewest[amount] != IMPOSSIBLE else -1


def coin_change_bfs(coins: list[int], amount: int) -> int:
    """BFS view: each level is one more coin, so the first hit is the fewest."""
    from collections import deque

    if amount == 0:
        return 0

    queue = deque([0])
    seen = {0}
    steps = 0

    while queue:
        steps += 1
        for _ in range(len(queue)):
            total = queue.popleft()
            for coin in coins:
                nxt = total + coin
                if nxt == amount:
                    return steps
                if nxt < amount and nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)

    return -1

Complexity Analysis

• Time — the outer loop runs amount times and the inner loop once per coin. Every cell is computed exactly once.
• Space — one array of amount + 1 entries. This cannot collapse to a few variables like House Robber, because fewest[a - c] may reach far back for a large coin.

Edge Cases

Related Problems

• Climbing Stairs — the same build-up, counting ways instead of minimising
• House Robber — a DP whose window is small enough to collapse to two variables
• Combination Sum — the same reuse rule, but listing every combination rather than the best
• Greedy — when taking the local best is provably safe