Coin change (DP)
mediumdp[a] is the fewest coins that make a. Every entry depends only on smaller amounts, so a single left-to-right pass is enough - and unlike greedy, it is always right.
O(amount × coins)Space O(amount)Saved in this browser - no sign-up, nothing sent anywhere.
How coin change (dp) works
dp[a] answers one question: what is the fewest coins that sum to a? dp[0] is 0 - making nothing takes nothing - and every other entry starts at infinity, meaning not yet reachable. To fill dp[a], try each coin c that fits: paying with c leaves the smaller amount a - c, so the candidate cost is dp[a - c] + 1. Take the minimum over all coins.
The naive recursion re-solves the same amounts constantly - make(6) calls make(5), make(3) and make(2), and each of those branches into overlapping amounts again, an exponential tree. But there are only amount + 1 distinct subproblems: with coins 1, 3, 4 and amount 24, the tree has millions of calls while the table has 25 entries. Filling them left to right, each exactly once, guarantees every value read is already final.
This is also the fix for greedy's blind spot. Greedy grabs the largest coin and commits: with coins 1, 3, 4 and amount 6 it takes 4 + 1 + 1 and never reconsiders. The table evaluates every coin at every amount, so the 3 + 3 answer cannot be missed. Reach for this shape whenever an early choice can strand you.
Step by step
- Take coins 1, 3, 4 and amount 6. Start with dp[0] = 0 and dp[1] through dp[6] at infinity.
- dp[1]: only coin 1 fits, and dp[0] + 1 = 1. dp[2] follows the same way: dp[1] + 1 = 2.
- dp[3]: coin 1 offers dp[2] + 1 = 3, but coin 3 offers dp[0] + 1 = 1. The minimum wins.
- dp[4]: coin 4 reaches back to dp[0] and records 1. Coins 1 and 3 both offered 2, and lose.
- dp[5]: the best is 2, via coin 1 on dp[4] or coin 4 on dp[1]. Either way, two coins.
- dp[6]: coin 3 on dp[3] gives 1 + 1 = 2, beating the 3 that coins 1 and 4 each offer.
- The answer is 2 coins. Walking the recorded winning coins back - 3 from 6, then 3 from 3 - recovers the combination 3 + 3.
Complexity
| Worst case time | O(amount × coins) |
|---|---|
| Space | O(amount) |
Pseudo-polynomial: the cost depends on the numeric value of the target.
Reference implementation
Python
def coin_change(coins, amount):
"""Fewest coins summing to amount, or -1."""
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == INF else dp[amount]JavaScript
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}Java
static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // stands in for infinity
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}Worth noticing
One subproblem per amount
dp[a] is 'the fewest coins that make a'. Every entry depends only on smaller amounts, so filling left to right guarantees the values it reads are already final.
Infinity means unreachable, and it propagates correctly
dp[a] stays infinite when no coin combination reaches a. Adding 1 to infinity is still infinite, so unreachable amounts never contaminate reachable ones - which is why the sentinel matters.
Unlike greedy, it cannot be trapped
With coins 1, 3, 4 and amount 6, greedy takes 4+1+1. The table considers every coin at every amount and finds 3+3. No first choice can lead it astray.
O(amount × coins), pseudo-polynomial
The cost depends on the numeric value of the amount, not just how many coins there are. Double the amount and the work doubles - which is why huge targets need a different approach entirely.
Common pitfalls
- Initialising the table with 0 instead of infinity. The min then always keeps the 0, and every amount claims to be free.
- Forgetting the coin <= a guard. dp[a - c] with a negative index reads out of bounds - in JavaScript it yields undefined and the min silently becomes NaN.
- Returning dp[amount] without checking for the sentinel. An unreachable amount should report -1, not infinity - or not amount + 1, if that was the stand-in.
- Adding 1 to a fake infinity that can overflow. The Java version fills with amount + 1 precisely so the + 1 stays in range.
- Assuming greedy would have been fine. It is - for canonical systems like 1, 5, 10, 25. Coins 1, 3, 4 break it at amount 6.
Where it is used
- Making change in point-of-sale and vending systems, where denominations are not guaranteed canonical.
- Minimum-operations problems - fewest steps, fewest jumps, fewest inserts - that decompose by a numeric amount.
- The unbounded knapsack family: allocating a budget across options that can each be reused.
- LeetCode 322 and its variants, one of the most common first DP questions in interviews.
Frequently asked questions
What is the time and space complexity of the coin change DP?
Time is O(amount × coins) - the table has amount + 1 entries and each one tries every coin. Space is O(amount) for the one-dimensional array. The cost is pseudo-polynomial: it scales with the numeric value of the target, so doubling the amount doubles the work.
Why does greedy fail for coin change?
Greedy commits to the largest coin that fits and never revisits the choice. With coins 1, 3, 4 and amount 6 it takes 4 + 1 + 1 for three coins, while 3 + 3 does it in two. Only canonical coin systems make greedy safe, and arbitrary denomination sets usually are not.
Is coin change the same as knapsack?
It is the unbounded knapsack in disguise: every coin can be reused any number of times, and the amount plays the role of capacity. The 0/1 knapsack differs in exactly one way - each item can be taken once - which is why its 1-D loop must run backwards while this one runs forwards.
How do I get the actual coins, not just the count?
Record which coin produced each minimum - a second array holding the winning coin for every amount. Starting at the target, repeatedly emit that coin and subtract it until you reach 0. The visualizer's final step performs exactly this walk to print one optimal combination.