322. Coin Change — DSA Atlas

322

MediumOne-Dimensional Dynamic ProgrammingBottom-up dynamic programming over amountsUnbounded knapsack (min coins)

Coin Change

Given an array coins of distinct coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. You may use each denomination unlimited times. If the amount cannot be formed, return -1.

Open official problem prompt ↗

In plain English

Find the smallest possible number of coins whose values add up exactly to the target amount, or prove it is impossible.

Picture it like this

Making change at a register: to hand over N cents in as few coins as possible you consider dropping the total by each coin you own and reuse the already-computed best for the remainder.

Example

Input: coins = [1, 2, 5], amount = 11
Output: 3
Why: 11 = 5 + 5 + 1 uses three coins, and no combination uses fewer.

Constraints

1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4

Pattern lesson

See the pattern, then code

Unbounded knapsack (min coins)

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. The fewest coins for amount a is one more than the fewest coins for a - c, minimized over every coin c that fits.

New words, made simpleKnow these before the algorithm

Unbounded knapsack: Each item type may be picked any number of times.
Sentinel / INF: A value larger than any real answer used to mark 'not yet reachable'.
Subproblem dp[a]: The fewest coins that sum to exactly a.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Greedy largest-first

Wrong in general, e.g. coins [1,3,4], amount 6 gives 4+1+1 instead of 3+3.

Always take the biggest coin that fits.

Time O(amount)Space O(1)

Best choiceBottom-up DP over amounts

Correct and efficient for the given constraints.

Build dp[0..amount] where dp[a]=min over coins of dp[a-c]+1.

Time O(amount * coins)Space O(amount)

The rule we keep true

Invariant

When the outer loop reaches a, dp[a] already equals the minimum number of coins to form a using any denominations, because all smaller amounts are finalized.

Why this is correct

Reasoning

Every optimal solution for amount a must have a last coin c; removing it leaves an optimal solution for a-c (exchange argument). Trying all c and adding one covers every possible last coin, so the minimum over them is optimal. Amounts are solved in increasing order so dp[a-c] is ready.

The algorithm in three movesSay these aloud before coding

1Create dp of size amount+1 with dp[0]=0 and the rest set to an unreachable sentinel

dp[5]=1 (one 5-coin)

2For each amount a from 1 up, try every coin c <= a

dp[10]=2 (two 5-coins)

3Set dp[a] = min(dp[a], dp[a-c] + 1)

dp[11]=dp[6]+1=3

4Return dp[amount], or -1 if it stayed unreachable

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readamount=11

2 · AskSet base cases.

3 · Update statedp[0]=0, dp[1..11]=12

4 · ResultOnly amount 0 is reachable so far.

Key takeaway

dp indexed by target amount; each cell is the minimum coins to build that amount.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Table and sentinel
amount+1 is larger than any achievable coin count, so it safely marks unreachable amounts; dp[0]=0 seeds the recurrence.
2
Lines 5-8Fill in increasing order
For each amount try every coin that fits and relax dp[a] using the already-final dp[a-c].
3
Lines 9Decode the result
If dp[amount] still exceeds amount it was never relaxed, meaning the target is impossible, so return -1.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

amount = 0 returns 0 with no coins
A single coin that does not divide the amount and no 1-coin returns -1
Coin larger than amount is simply skipped
Distinct denominations only (guaranteed)

Common beginner mistakes

Using a greedy largest-coin heuristic, which fails for non-canonical coin systems
Comparing dp[amount] against the wrong sentinel and misreporting -1
Iterating amounts in the wrong nesting so dp[a-c] is not yet computed

Check your understanding

Why return -1 by checking dp[amount] <= amount rather than == some INF constant?

Coin Change

Coin Change

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming