DPAlgorithmaka minimum coins, change-making problem

Coin Change

Find the fewest coins that sum to an amount (or count the ways) using unlimited coins of given denominations.

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

Given coin denominations coins and a target amount, return the minimum number of coins whose values sum to amount, or -1 if impossible. A second common version asks for the *number of distinct combinations* instead. Both are Unbounded Knapsack specializations: weight = value = the coin, "value" = 1 coin (minimize) or 1 way (count).

Greedy (largest coin first) works for canonical systems like {1, 5, 10, 25} but fails in general: with coins {1, 3, 4} and amount 6, greedy takes 4+1+1 (3 coins) while 3+3 uses 2. DP handles every system in O(amount · k).

1D DPunbounded knapsackmin-pluscountingO(amount·k)

Intuition

A mental model before the formal terms.

Coins {1, 2, 5}, amount 11. Ask: what is the last coin in an optimal solution? If it is a 5, the rest makes 6 optimally; if a 2, the rest makes 9; if a 1, the rest makes 10. So min_coins(11) = 1 + min(min_coins(6), min_coins(9), min_coins(10)). Fill from small amounts upward: dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=1, dp[6]=2, dp[7]=2, dp[8]=3, dp[9]=3, dp[10]=2, dp[11]=3 (5+5+1).

Picture the amounts as rungs on a ladder. From each rung you can jump up by any coin value. dp[a] is the fewest jumps needed to land on rung a starting at 0 — it is a shortest path on a line graph where every edge costs 1, which is why BFS Shortest Path (Unweighted) over amounts also solves it.

How it works

  1. State: dp[a] = minimum number of coins summing to exactly a (∞ if impossible). For the counting version, dp[a] = number of combinations summing to a.
  2. Transition (min): dp[a] = 1 + min over coins c ≤ a of dp[a - c]. (count): dp[a] += dp[a - c].
  3. Base case: dp[0] = 0 coins (min) / dp[0] = 1 way (count); all other dp[a] = ∞ (min) / 0 (count).
  4. Iteration order: for the minimum, either loop order works (amount-outer over coins, or coin-outer ascending amount). For counting *combinations* the coin loop must be outer so that each unordered multiset is built in one canonical coin order; amount-outer would count 1+2 and 2+1 separately.
  5. Answer location: dp[amount], returning -1 if it is still ∞.
  6. Space optimization: the table is already 1D of size amount + 1. No further reduction is possible in general since dp[a - c] can reach back max(coins) positions.

Why it works

Optimal substructure: remove any one coin c from an optimal solution for a; the remaining coins form a solution for a - c, and it must be optimal for a - c (else swap in a smaller one and reduce the count for a). Taking the minimum over all possible last coins therefore yields the exact optimum.

∞ sentinels propagate impossibility correctly: dp[a] stays ∞ exactly when no coin subtraction reaches a reachable amount.

For counting, the coin-outer loop is an induction over prefixes of the coin list: after processing coins 1..j, dp[a] counts multisets using only those coins. Adding coin j and iterating a upward counts, for each a, the multisets whose largest-index coin is j, exactly once each.

Recognition

How to tell a problem wants this.

  • "Fewest number of X to reach a total", "unlimited supply", "return -1 if not possible".
  • "Number of ways to make amount" with order irrelevant — combinations, not permutations.
  • Amount ≤ 10^4–10^5 and coin count ≤ ~100 — the amount × k table fits.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

1
0
3
1
4
2
0123456
0∞∞∞∞∞∞
1/20dp[a] = fewest coins that sum to a. Amount 0 needs 0 coins; everything else starts at ∞ (unknown / impossible).
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Coin Change →
1dp[0] = 0; dp[1..A] = ∞
2for a in 1 .. A:
3  for coin in coins:
4    if coin <= a and dp[a-coin] + 1 < dp[a]:
5      dp[a] = dp[a-coin] + 1; from[a] = coin
6return dp[A] (∞ means impossible)
Variables
A6
Complexity
best O(amount · k)
avg O(amount · k)
worst O(amount · k)
space O(amount)
Speed

Pseudocode

1dp = array[amount + 1] filled with INF; dp[0] = 0
2for a in 1..amount:
3  for c in coins:
4    if c <= a and dp[a - c] + 1 < dp[a]:
5      dp[a] = dp[a - c] + 1
6return dp[amount] if dp[amount] != INF else -1

Implementations

1# dp[a] = fewest coins summing to exactly a (inf if impossible)
2def coin_change(coins: list[int], amount: int) -> int:
31 · State table
4    INF = float("inf")
5    dp: list[float] = [INF] * (amount + 1)
62 · Base case
7    dp[0] = 0  # zero coins make amount 0
83 · Transition
9    for a in range(1, amount + 1):
10        for c in coins:
11            if c <= a and dp[a - c] + 1 < dp[a]:
12                dp[a] = dp[a - c] + 1
134 · Answer
14    return -1 if dp[amount] == INF else int(dp[amount])
15 
16 
17# Coin Change II: number of combinations — coins must be the OUTER loop
18def coin_change_ways(coins: list[int], amount: int) -> int:
19    dp = [0] * (amount + 1)
20    dp[0] = 1
21    for c in coins:
22        for a in range(c, amount + 1):
23            dp[a] += dp[a - c]
24    return dp[amount]
Walkthrough
  1. float("inf") is the idiomatic sentinel; the table is typed list[float] because it mixes inf with ints.
  2. dp[0] = 0 seeds the empty combination; every other amount starts unreachable.
  3. The c <= a guard is essential: dp[a - c] with a negative index would silently wrap to the END of the list in Python.
  4. The answer converts back with int(...) so callers get an int, not a float, when the amount is reachable.
  5. coin_change_ways puts coins outer: after processing a prefix of coins, dp[a] counts multisets using only those coins.
Complexity (this implementation)
time O(amount · k) · space O(amount)

Python ints are arbitrary precision, so the counting variant never overflows — it just gets slower as numbers grow.

Language notes
  • Negative list indices are legal Python (dp[-1] is the last element), which turns a missing guard into a wrong answer instead of an error.
  • float("inf") compares correctly with ints; math.inf is the same value with an import.
  • For very large amounts the two nested pure-Python loops dominate; the same table in a bytearray/numpy or a BFS over amounts can be faster in practice.
Common mistakes in this language
  • Skipping the c <= a guard — negative indices wrap around silently.
  • Using amount + 1 as the sentinel but forgetting to translate it to -1 at the end.
  • Counting with the amount loop outside the coin loop (counts permutations).
Language differences that matter here
  • Infinity sentinel: JS/TS Infinity and Python float("inf") survive + 1 unchanged; C++ has no integer infinity — use 1e9 and compare with >=.
  • A negative dp[a - c] index is UB in C++, undefined → NaN in JS/TS, and wraps to the end of the list in Python — the c <= a guard is load-bearing in all four.
  • Combination counts: C++ needs long long, JS/TS are exact only below 2^53, Python is exact at any size.

Complexity

Best
O(amount · k)
Average
O(amount · k)
Worst
O(amount · k)
Space
O(amount)

k = number of denominations. BFS over amounts has the same bound but can stop early when the target is reached.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Minimum count of reusable parts that sum exactly to a target, in an arbitrary (non-canonical) denomination system.
  • Counting combinations of reusable parts (Coin Change II).
  • Any "shortest path on a number line with fixed jump sizes" question.
Avoid it when
  • Canonical coin systems where greedy is provably optimal and O(k) suffices — but only if you know the system is canonical.
  • Amount around 10^9 — the 1D table is too large; consider BFS with pruning for tiny coin sets or math.
  • Each coin available only once — that is 0/1 Knapsack with the downward loop.

Alternatives

Unbounded KnapsackBFS Shortest Path (Unweighted)Fractional Knapsack

Common mistakes

  • Using greedy largest-first and assuming optimality: fails on {1, 3, 4}, amount 6.
  • Initializing dp with 0 instead of ∞ — impossible amounts then look reachable with 0 coins.
  • Using Integer.MAX_VALUE as ∞ and overflowing on + 1. Use amount + 1 or MAX/2 as the sentinel.
  • Counting combinations with amount as the outer loop — that counts ordered sequences (permutations) instead.

Interview patterns

  • Coin Change (minimum coins) and Coin Change II (number of combinations).
  • Perfect Squares: coins are 1, 4, 9, …, ⌊√n⌋².
  • Combination Sum IV: permutations — amount outer, coins inner.
  • Minimum cost to reach a target with weighted steps — same recurrence with cost[c] instead of 1.
Interview questions on this
Mock interviews

Example problems

Combination SummediumCoin ChangemediumWord Breakmedium