Coin Change — Fewest Coins for a Target

The Problem

You have an unlimited supply of coins in denominations given by an array coins, and a target amount. Find the fewest coins that sum to exactly amount. If no combination reaches the target, return -1.

This looks superficially like a greedy problem — take the largest coin that fits, repeat. But greedy fails on many coin sets. With denominations [1, 3, 4] and amount 6, greedy picks 4 then 1+1 for three coins, while DP finds 3+3 for two.

Defining the Subproblem

Let dp[a] = the minimum number of coins needed to make amount a.

Base case: dp[0] = 0 — zero coins are needed to make amount zero.

Recurrence: for every amount a from 1 to amount, and every coin c in coins:

plaintext

We imagine using coin c once; the remaining amount a - c was already solved in a prior iteration. The minimum over all valid coins gives dp[a].

Sentinel value. We initialise dp[a] = amount + 1 for all a > 0. Any value strictly greater than amount acts as "infinity" — it can never be a valid coin count (you cannot need more than amount coins of denomination 1). If dp[amount] is still the sentinel at the end, no solution exists and we return -1.

Code

Walking Through an Example

Coins = [1, 2, 5], amount = 11.

a	0	1	2	3	4	5	6	7	8	9	10	11
dp[a]	0	1	1	2	2	1	2	2	3	3	2	3

dp[11] = 3, achieved with 5 + 5 + 1.

Notice dp[5] = 1 (one 5-coin), dp[10] = 2 (two 5-coins), then dp[11] = dp[10] + 1 = 3.

Complexity

Dimension	Cost
Time	O(amount · \|coins\|)
Space	O(amount)

Like knapsack, the complexity is pseudo-polynomial in amount. For typical interview inputs (amount ≤ 10 000) it is very fast.

Counting Ways (a Variant)

A close cousin asks for the number of ways to make amount rather than the minimum number of coins. The only changes are initialising dp[0] = 1 (one way to make zero: use no coins) and summing instead of taking the minimum:

python

Note the loop order is reversed: iterating coins in the outer loop and amounts in the inner loop prevents counting the same combination multiple times (it counts combinations, not permutations).

Further DP Table Examples

The same 1D DP-over-amounts pattern extends naturally to other sequence problems. Two important ones coming up in this stage:

Longest Common Subsequence (LCS) — a 2D table over two strings, filling dp[i][j] = length of LCS of s1[:i] and s2[:j].
Longest Increasing Subsequence (LIS) — a 1D table (or patience-sort variant), filling dp[i] = length of longest increasing subsequence ending at index i.

Both follow the same discipline: define what a cell means, write the recurrence, fill the table in dependency order.

Interactive Lab

Key Takeaways

Define dp[a] = minimum coins for amount a, initialise with a sentinel larger than any valid answer.
The recurrence tries every coin and takes the best: dp[a] = min over c of dp[a-c] + 1.
Time O(amount · #coins), space O(amount) — simple 1D DP.
Changing min to addition and swapping the sentinel for 0 gives the "count ways" variant.
The pattern generalises to LCS, LIS, edit distance, and many other problems — each is just a different recurrence over a carefully chosen subproblem definition.