What Is the Coin Change Problem?
Coin Change finds the fewest coins needed to make a target amount from given coin denominations (each coin may be used many times). A generalization of making change, it's a classic introductory DP problem.
The one-line idea: "the answer for amount a is built from the answers for smaller amounts." You fill upward starting from the smallest amounts.
Why Greedy Fails
The greedy "grab the largest coin first" approach can be wrong depending on the denominations.
Making 6 from coins {1, 3, 4}:
- •Greedy: 4 + 1 + 1 = 3 coins
- •Optimal: 3 + 3 = 2 coins
Because greedy breaks like this, you need DP that considers every possibility.
State and Recurrence
dp[a] = the fewest coins needed to make amount a.
Viewing each coin c as the last one added:
dp[a] = min( dp[a - c] + 1 ) (over all coins c with a ≥ c)
Base: dp[0] = 0 (zero needs zero coins).
How It Works
Step 1. Set dp[0] = 0 and the rest to a large "unreachable" value (∞).
Step 2. Increase amount a from 1 to the target; for each coin c, update if dp[a-c] + 1 is smaller.
Step 3. dp[target] is the answer. If it's still ∞, those coins can't make it (return -1).
The AlgoNote visualization shows, as the amount grows, which coin fills each cell, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(amount × coins) |
| Space | O(amount) |
Walking Through an Example
Coins {1, 3, 4}, target 6.
- •dp[1]=1, dp[2]=2, dp[3]=1 (coin 3)
- •dp[4]=1 (coin 4), dp[5]=2 (4+1), dp[6]=2 (3+3)
dp[6] = 2 is the answer.
Common Mistakes
- •Unreachable handling: adding 1 to ∞ before comparing can overflow or give wrong answers; check whether
dp[a-c]is ∞ first. - •Fewest vs count of ways: "number of ways to make it" uses a different recurrence (put the coin loop on the outside to avoid duplicate combinations).
- •Missing base case: forgetting
dp[0] = 0makes everything unreachable.
See It in Action on AlgoNote
Watch the table fill from small amounts and see which coin minimizes each amount, step by step on AlgoNote.