Given coin denominations and an amount, return the fewest coins that make the amount, or -1 if it cannot be made. You have unlimited coins of each type.
Restating the Problem: You are a cashier tasked with returning a specific amount of change, but you want to give the customer the fewest physical coins possible. You have a bottomless drawer of each coin denomination provided.
Constraints to Note:
The amount can be up to 10^4.
You can have up to 12 different coin denominations.
A coin's value can be up to 2^{31} - 1.
Because of the amount limit, an O(Amount \times Coins) algorithm will take at most 120,000 operations, which is incredibly fast.
The brute force method is to explore every possible coin choice. At each step, if we need to make amount A, we try subtracting each coin denomination C. Then we recursively find the fewest coins to make A - C. Since we can reuse coins, each recursive step branches into K paths (where K is the number of coin types). The depth of the recursion can be up to Amount (if we just use 1-cent coins). This yields a time complexity of O(K^{Amount}). For amount=11 and 3 coins, that's 3^{11} \approx 177,000. For amount=10,000, it's literally impossible to compute in a human lifetime. We must memoize or use DP.
This is the standard example for the DP-versus-greedy question from 4.22, so have the counterexample ready.
Greedy rule: always take the largest coin that fits.
Counterexample:coins = [1, 3, 4], amount = 6. Greedy takes 4, then 1, then 1 — three coins. The right answer is 3 + 3 — two coins.
Real currencies are deliberately designed so that greedy works, which is exactly why the intuition is so strong and so wrong. When the denominations are arbitrary, greedy is not safe, and one counterexample settles it.
Read aloud: the cheapest way to make a is one coin, plus the cheapest way to make whatever was left after that coin. Try every coin as the last one and keep the best.
dp[0] = 0 — making zero needs no coins. That is the base case and everything builds from it.
Here dp[a] means "the fewest coins that add up to exactly a".
(1) A stand-in for "impossible". No amount needs more than amount coins, even using only coins of 1. So amount + 1 can never be a real answer, and it is safe to use as "cannot be made". It is used instead of infinity so that 1 + INF stays an ordinary number.
(2) Every amount starts as impossible.
(3) An amount of 0 needs 0 coins. Every other answer is built on this one.
(4) Work out every amount from 1 up to the target. Smaller amounts are always finished first, because each answer is built from smaller ones.
(5) Try each coin as the last coin used.
(6) The coin must not be bigger than the amount.
(7) Using coin c last costs one coin plus the fewest coins for what is left, a − c. Keep the smallest result over all coins. In TypeScript the same step is on line (6), written on one line.
(8) If the target is still "impossible", return −1.
INF = amount + 1 rather than infinity. The most coins any reachable amount could need is amount (all 1s), so amount + 1 is unreachable and marks "impossible" without needing floats. It also keeps 1 + dp[...] safe from overflow concerns in typed languages.
The loop order.dp[a] reads dp[a - c], which is always smaller, so the outer loop counts upwards and every cell it needs is already filled.
Coins may be reused freely, and the code allows that automatically: dp[a - c] may itself have used coin c. Compare 4.23.12 Partition Equal Subset Sum, where each item is used once, and the loop must run downwards to prevent reuse. That loop direction is the entire difference between the two problems. It is the mistake named in 4.22.
from functools import lru_cachedef coinChange(self, coins, amount): @lru_cache(None) def fewest(a: int) -> float: if a == 0: return 0 if a < 0: return float('inf') return min((1 + fewest(a - c) for c in coins), default=float('inf')) result = fewest(amount) return -1 if result == float('inf') else result
Easier to derive, because it is just the recurrence written down. It costs stack depth and hash lookups, and it computes only the amounts actually reachable — which is a genuine advantage when the coins are large and most amounts are unreachable.
O(\text{amount} \times \text{number of coins}) time, O(\text{amount}) space.
Time Complexity Derivation: We have an outer loop running from 1 to amount (which is O(\text{amount}) iterations). Inside that, we loop through all C coin denominations (which is O(\text{coins}) iterations). The operation inside the inner loop is an O(1) constant-time lookup and addition. Multiplying these gives O(\text{amount} \times \text{coins}).
Space Complexity Derivation: We create a 1D array dp of size amount + 1 to store the fewest coins for every amount up to the target. This directly takes O(\text{amount}) memory. We don't use any other data structures.
This is pseudo-polynomial. The runtime is polynomial in the value of the amount, not in the number of digits used to write it. Adding one more digit to the amount multiplies the work by ten. Coin Change is a cousin of the knapsack problem for exactly this reason, and 4.29 explains why that matters.
Coin Change II — count the number of combinations rather than the fewest coins. The loop order flips: coins outside, amounts inside, or you count permutations by accident. That is 4.24.4 and it is one of the most instructive loop-order lessons in the book.
Combination Sum IV — counts permutations, so the loops go the other way round. Compare the two and the difference becomes obvious.
Perfect Squares — Coin Change where the coins are 1, 4, 9, 16 and so on.
Minimum Cost For Tickets — the same shape with three "coins" of different durations.
"Why not greedy?"[1, 3, 4] and amount 6. Have it ready before they ask.
"What does dp[a] mean?" The fewest coins making exactly a.
"Why dp[0] = 0?" Zero needs no coins, and every other value is built from it.
"How do you mark impossible?" A sentinel larger than any real answer, then convert to -1 at the end.
"Why does the loop go upwards, and when would it go down?" Upwards allows reuse. Downwards prevents it, which is what 0/1 knapsack needs.
"What is the complexity, and is that polynomial?"O(\text{amount} \times \text{coins}), and it is pseudo-polynomial — polynomial in the value, not in the input size.
"How would you return the actual coins?" Store, for each amount, which coin gave the best answer, then walk backwards from amount. Reconstruction needs the table, which is the one thing the O(1)-space tricks give up.
One thing to volunteer: open with the greedy counterexample. It settles the technique choice in ten seconds and shows you tested your first instinct instead of trusting it.
Next:4.23.9 Maximum Product Subarray — where you have to carry two values because a negative can turn the worst into the best.