Coin Change LeetCode Solution: Complete DP Walkthrough

If there is one problem that teaches dynamic programming, it is Coin Change. LeetCode 322 is the problem that coding bootcamps, university courses, and interview prep guides all converge on when they need to explain what DP actually is and why it matters. If you understand coin change leetcode at a deep level, you understand the core of dynamic programming.

The reason Coin Change is so effective as a teaching tool is that it naturally resists simpler strategies. You cannot sort your way out of it. You cannot use two pointers. The greedy approach — which feels intuitive — fails on certain inputs. This forces you to confront the fundamental question DP answers: how do you build optimal solutions from overlapping subproblems?

This walkthrough takes you from the problem statement through the greedy trap, into the recursive solution with memoization, and finally to the clean bottom-up tabulation that interviewers want to see. By the end, you will not just know how to solve Coin Change — you will understand the DP framework that transfers to dozens of other problems.

LeetCode 322 gives you an integer array coins representing coin denominations and an integer amount representing a target sum. You need to return the fewest number of coins that make up that amount. If no combination of coins can reach the target, return -1. You have an infinite supply of each coin denomination — this is what makes it an unbounded knapsack variant.

For example, given coins = [1, 5, 11] and amount = 15, the answer is 3 because you can use three 5-cent coins. Given coins = [2] and amount = 3, the answer is -1 because no combination of 2-cent coins can make 3 cents.

The problem looks simple on the surface, and that simplicity is deceptive. The constraints — unlimited coin usage and minimum count optimization — create a search space that grows exponentially if you explore it naively. This is exactly the kind of structure where dynamic programming shines.

The first instinct most people have is greedy: always pick the largest coin that fits. This works perfectly for US currency denominations (25, 10, 5, 1) — you can prove that greedily choosing the largest coin always yields the minimum count for that specific set. But coin change leetcode is not limited to US denominations, and that is where greedy breaks down.

Consider coins = [1, 3, 4] with amount = 6. The greedy approach picks 4 first (leaving 2), then 1 twice, giving 4 + 1 + 1 = 3 coins. But the optimal answer is just 2 coins: 3 + 3. Greedy missed this because it committed to the locally optimal choice (the biggest coin) without considering that a smaller coin might lead to a globally better outcome.

This counterexample is the classic motivation for dynamic programming. When local decisions do not guarantee global optimality, you need a method that considers all possibilities systematically. That method is DP — and the minimum coins problem is the cleanest demonstration of why it exists.

The recursive approach defines a function dp(amount) that returns the minimum number of coins needed to make that amount. The base case is dp(0) = 0 — you need zero coins to make zero. For any other amount, you try subtracting each coin denomination and take the minimum result plus one.

The recurrence relation is: dp(amount) = min(dp(amount - coin) + 1) for each coin in coins, where amount - coin >= 0. If no coin leads to a valid solution, dp(amount) = -1. This directly mirrors the decision at each step: which coin should I pick next to minimize the total count?

Without memoization, this recursion has exponential time complexity because it recomputes the same subproblems repeatedly. For example, dp(11) with coins [1, 5] would compute dp(6) multiple times through different paths. Adding a memo table — a hash map or array storing already-computed results — reduces the time complexity to O(amount * coins.length) and space to O(amount).

The memoized recursive solution is often easier to write and reason about because it maps directly to the recurrence relation. You define the subproblem, write the base case, express the recurrence, and add caching. Many candidates find this the most natural starting point before optimizing to bottom-up.

The bottom-up approach builds the solution iteratively from dp[0] up to dp[amount]. You create an array of size amount + 1, initialize dp[0] = 0, and fill every other entry with a sentinel value like amount + 1 (which represents "impossible" since you can never need more than amount coins even with denomination 1).

For each value i from 1 to amount, you iterate over every coin. If coin <= i and dp[i - coin] + 1 < dp[i], you update dp[i]. After filling the entire table, dp[amount] contains your answer — unless it still equals the sentinel, in which case you return -1.

The time complexity is O(amount * coins.length) and space is O(amount), identical to the memoized version. The advantage of bottom-up is that it avoids recursion stack overhead and is typically faster in practice due to better cache locality. Most interviewers prefer seeing the bottom-up solution because it demonstrates that you can translate a recurrence into iterative code.

The coin change bottom up approach is also easier to analyze for correctness. You can trace through the array for small examples and verify each entry. For coins = [1, 3, 4] and amount = 6, the dp array builds as: [0, 1, 2, 1, 1, 2, 2]. The answer dp[6] = 2 corresponds to using two coins of denomination 3.

Several edge cases appear frequently in interviews and on LeetCode submissions. When amount = 0, the answer is always 0 regardless of the coin denominations — you need zero coins to make zero. When no combination of coins can reach the target (like coins = [2] with amount = 3), you must return -1. Your sentinel initialization handles this naturally.

A common variant is Coin Change II (LeetCode #518), which asks for the number of combinations that make up the amount rather than the minimum count. This changes the recurrence: instead of taking the minimum, you sum the ways. The state definition and iteration order also change — you iterate coins in the outer loop to avoid counting permutations as different combinations.

Both problems are instances of the unbounded knapsack pattern. In unbounded knapsack, items (coins) can be used unlimited times, and you optimize some objective (minimum count or total ways). Recognizing this connection lets you apply the same framework to problems like Perfect Squares (#279), Integer Break (#343), and Combination Sum IV (#377).

Coin Change is not just one problem — it is a template for solving dynamic programming problems in general. The framework you use here transfers directly: define the state (what does dp[i] represent?), write the recurrence (how does dp[i] relate to smaller subproblems?), set the base case, and choose top-down or bottom-up implementation.

This same framework solves over 30 LeetCode DP problems. Once you internalize the pattern from Coin Change, problems like House Robber (#198), Longest Increasing Subsequence (#300), and Word Break (#139) become variations on the same theme. The state definition changes, the recurrence changes, but the approach stays constant.

The dynamic programming coin change problem also teaches you the most important meta-skill for interviews: recognizing when DP applies. If a problem asks for an optimal value (minimum, maximum, count) and has overlapping subproblems with optimal substructure, DP is likely the right tool. Coin Change makes that recognition intuitive because the greedy failure is so clear.

Practice implementing both the top-down and bottom-up versions until you can write either from memory. Then move on to related problems and notice how the framework repeats. YeetCode flashcards help you drill this pattern recognition — reviewing the recurrence relations and state definitions across DP problems builds the recall speed you need under interview pressure.