Coin Change LeetCode 322 — DP Deep Dive

LeetCode 322 Coin Change gives you an array of coin denominations and a target amount. Your task is to find the minimum number of coins needed to make exactly that amount. If no combination of coins can reach the target, return -1. Each denomination can be used any number of times — you have an unlimited supply of every coin type.

The problem is deceptively simple to state but requires careful algorithmic thinking. With coins [1, 5, 10, 25] and typical amounts, intuition says to always grab the largest coin — but this greedy approach fails on certain denomination sets. A complete search over all combinations works but is exponential. Dynamic programming gives the optimal O(amount × coins) solution.

This problem appears constantly in technical interviews because it cleanly demonstrates why greedy fails, introduces unbounded knapsack DP, and has an elegant BFS interpretation. Understanding it deeply unlocks an entire family of DP problems including Coin Change II, Combination Sum IV, and the general unbounded knapsack template.

The greedy strategy for coin change is: repeatedly pick the largest coin denomination that does not exceed the remaining amount. For standard currency systems like US coins [1, 5, 10, 25], greedy always works because the denominations are carefully designed to be compatible. But for arbitrary coin sets, greedy fails.

Consider coins [1, 3, 4] and amount 6. Greedy picks 4 first (largest ≤ 6), leaving 2. Then picks 1, leaving 1. Then picks 1 again. Total: 4 + 1 + 1 = 3 coins. But the optimal solution is 3 + 3 = 2 coins. Greedy committed to using the 4-coin too early and got stuck needing two 1-coins to bridge the gap, missing the cleaner two-3 solution.

The root cause is that greedy makes locally optimal choices without considering future consequences. Using a large coin might be locally best (it covers the most ground) but globally suboptimal (it leaves a remainder that requires many small coins). DP avoids this by computing the optimal answer for every sub-amount first, then building up to the target — guaranteeing the global minimum.

Define dp[i] as the minimum number of coins needed to make amount i exactly. The base case is dp[0] = 0: it takes zero coins to make amount 0. Initialize all other entries to infinity (or amount+1, since you can never need more than amount coins if each coin has value at least 1).

For each amount from 1 to target, iterate over every coin denomination. If the coin value is less than or equal to the current amount, then dp[amount] = min(dp[amount], dp[amount - coin] + 1). This recurrence says: the minimum coins for amount i is either what we already found, or one more than the minimum coins for (i - coin). After filling the table, return dp[amount] if it is not infinity, or -1 if it remains unreachable.

The time complexity is O(amount × coins) — for each of the amount+1 entries we try each coin. Space is O(amount) for the dp array. This is optimal for the general case; no known polynomial algorithm does better for arbitrary coin denominations.

Coin Change is a special case of the unbounded knapsack problem. In the classical 0/1 knapsack, each item can be used at most once. In bounded knapsack, each item has a finite count. In unbounded knapsack, each item can be used any number of times — exactly like our coin denominations.

The unbounded knapsack template has an outer loop over capacity (amount) and an inner loop over items (coins). Because an item can be reused, you iterate capacity in ascending order and items in any order. Contrast with 0/1 knapsack where you iterate capacity in descending order to prevent using the same item twice. Coin Change uses ascending order for amount — and so does any unbounded variant.

The Coin Change II problem (LeetCode 518) asks for the number of combinations instead of minimum count. It uses the same loop structure but with addition instead of min. Understanding that both problems share the same unbounded knapsack skeleton — only the recurrence and goal differ — lets you recognize and solve the entire family rapidly.

There is an elegant BFS interpretation of Coin Change. Treat each possible amount 0 through target as a node in a graph. For each node representing amount i and each coin denomination c, there is a directed edge from i to i+c (or equivalently, from i to i-c in reverse). The problem asks: what is the shortest path (fewest edges) from node 0 to node target?

BFS explores nodes level by level, where each level represents one more coin used. Start with amount 0 at level 0. At each BFS step, expand the current frontier by adding each coin denomination. The first time you reach the target amount, the current level is the answer — BFS guarantees the shortest path in an unweighted graph.

BFS has the same O(amount × coins) time complexity as DP but typically uses more memory due to the queue. However, BFS is often more intuitive for people who think in graph terms, and it naturally handles the -1 case: if the BFS queue empties before reaching the target, return -1. Both DP and BFS are correct and efficient; which you use depends on how the interviewer wants you to frame it.

Python DP: def coinChange(coins, amount): dp = [float("inf")] * (amount + 1); dp[0] = 0; for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1); return dp[amount] if dp[amount] != float("inf") else -1. This is 6 lines. Initialize with float("inf") so any real solution is smaller. dp[0] = 0 is the base case. The nested loop is the recurrence. The final check converts unreachable infinity to -1.

Java DP: public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } In Java, use amount+1 as the sentinel instead of Integer.MAX_VALUE to avoid overflow when doing dp[i-coin]+1. The return condition dp[amount] > amount catches the impossible case because you can never need more coins than the amount itself (minimum coin value is 1).

Both implementations run in O(amount * coins) time and O(amount) space. For amount = 10,000 and 12 coins, this is 120,000 operations — extremely fast. The DP table is reusable: if you need answers for multiple amounts with the same coins, compute the full table once and look up each amount in O(1).

Coin Change II (LeetCode 518) asks for the number of distinct combinations (not minimum count). The DP recurrence changes from min to sum: dp[i] += dp[i - coin] for each coin. The loop order (outer coins, inner amount) ensures each combination is counted once. Recognizing that Coin Change and Coin Change II share the same structure but differ in operator and loop order is the key insight for mastering both.

Combination Sum IV (LeetCode 377) asks for the number of ordered sequences (permutations) summing to the target. It uses outer=amount, inner=coins — the reverse of Coin Change II — because order matters. Target Sum (LeetCode 494) uses a similar additive DP. All three are variants of the unbounded knapsack: reuse allowed, different counting objectives.

For interviews, the progression is: Coin Change (min coins) → Coin Change II (count combos) → Combination Sum IV (count perms) → general unbounded knapsack. Once you understand how the loop order and recurrence operator change between these problems, you can derive any variant on the fly. Coin Change (LeetCode 322) is the ideal entry point because it has the simplest recurrence and the most intuitive BFS alternative.