Coin Change: Classic Dynamic Programming

You have coins of different denominations and a target amount of money. What is the fewest coins you need to make that amount? If it is impossible, return -1.

This is LeetCode 322: Coin Change, and it is one of the most important dynamic programming problems you will encounter. It is the textbook example of the unbounded knapsack pattern, and once you understand how to fill the DP table here, you will recognize the same approach in dozens of other problems.

Why this problem matters

Coin Change sits right at the sweet spot between "too easy to learn anything" and "too hard to start with." It forces you to think about:

• Optimal substructure: the best solution for amount n depends on the best solutions for smaller amounts.
• Overlapping subproblems: many different paths lead to the same sub-amount, and you do not want to recompute them.
• Multiple choices at each step: unlike Climbing Stairs where you always pick from 1 or 2 steps, here the set of choices (coins) can be anything.

If Climbing Stairs is your first DP problem, Coin Change should be your second. It takes the same core idea and adds a layer of decision-making that makes the pattern more general.

Starting with recursion

The recursive thinking is straightforward. To find the minimum coins for amount n, try using each coin. For each coin c where c <= n, the answer could be 1 + minCoins(n - c). Take the minimum across all coins.

def coin_change(coins, amount):
    def helper(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')

        best = float('inf')
        for coin in coins:
            result = helper(remaining - coin)
            best = min(best, result + 1)

        return best

    ans = helper(amount)
    return ans if ans != float('inf') else -1

This works but it is painfully slow. For coins = [1, 3, 4] and amount = 6, the recursion tree branches at every level. Many sub-amounts get computed over and over. The time complexity is O(amount^n) where n is the number of coins. That is exponential and will time out on anything nontrivial.

Adding memoization (top-down DP)

Cache each sub-amount so you compute it only once.

def coin_change(coins, amount):
    memo = {}

    def helper(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]

        best = float('inf')
        for coin in coins:
            result = helper(remaining - coin)
            best = min(best, result + 1)

        memo[remaining] = best
        return best

    ans = helper(amount)
    return ans if ans != float('inf') else -1

Now each amount from 0 to amount is solved once. Time: O(amount * len(coins)). Space: O(amount) for the memo table plus O(amount) for the call stack. Much better, but we can do cleaner.

Building the DP table (bottom-up)

Instead of recursing from the top, build up from amount 0. Define dp[i] as the minimum number of coins needed to make amount i.

The recurrence:

• dp[0] = 0 (zero coins needed for amount 0)
• For each amount i from 1 to amount, try every coin c: if c <= i, then dp[i] = min(dp[i], dp[i - c] + 1)
• Initialize every cell to infinity (meaning "impossible so far")

Let's trace through coins = [1, 3, 4] and amount = 6:

The key insight in every step: for the current amount, you look back at dp[amount - coin] for each coin. You are asking, "if I used this coin, how many coins did I need for the remaining amount?" Then you pick the option that gives the smallest total.

def coin_change(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

Time: O(amount * len(coins)). Two nested loops.

Space: O(amount). One array of length amount + 1.

No recursion, no call stack, no memo dictionary overhead. Just a simple nested loop that fills a table from left to right.

Can we optimize space further?

In Climbing Stairs, we optimized from O(n) to O(1) because each cell only looked at the previous two. Here, dp[i] can look back as far as the largest coin value. In general, you need the full array because a coin of value 1 looks back one step while a coin of value 100 looks back 100 steps. You cannot predict which cells you will need.

So O(amount) space is already optimal for this problem. That is fine. Knowing when you can optimize space and when you cannot is just as important as knowing the trick itself.

Complexity analysis

Where n is the number of coin denominations.

The bottom-up approach is the most practical. Same time as memoized recursion, but without recursion depth concerns and with better constant factors.

Edge cases to watch for

• amount = 0: return 0. You need zero coins to make zero.
• No valid combination: e.g., coins = [2] and amount = 3. Every reachable cell stays at infinity. Return -1.
• Single coin: coins = [5], amount = 15. Just check if amount is divisible by the coin.
• Coin equals amount: coins = [7], amount = 7. dp[7] = dp[0] + 1 = 1.
• Large amounts: the DP table can be up to 10,000 entries (per LeetCode constraints), which is fine.

The building blocks

This problem is built on linear DP with constant state, the same fundamental pattern as Climbing Stairs. The structure is the same: iterate through a sequence of amounts, and at each position compute a value based on previously computed values.

The difference is in the transition. In Climbing Stairs, the lookback is always exactly 2 positions. In Coin Change, the lookback depends on which coins are available. But the core approach is identical:

• State: dp[i] = minimum coins for amount i
• Transition: dp[i] = min(dp[i - coin] + 1) over all coins
• Base case: dp[0] = 0

This same building block shows up in many other problems:

• Perfect Squares (LeetCode 279): replace "coins" with "perfect squares." Exact same DP structure.
• Minimum Cost for Tickets (LeetCode 983): replace coin values with ticket durations (1, 7, 30 days). Same idea of picking the best option at each step.
• Word Break (LeetCode 139): at each position, try every word in the dictionary. If the word fits, check the DP value at the position before it.

Once you see the shared pattern, these problems become variations on a theme rather than separate challenges.

From understanding to recall

Reading through this walkthrough, you can probably follow every step. But will you be able to reproduce the solution in a week without looking at notes? What about in an interview, with someone watching?

Understanding and recall are different skills. The gap between "I get it" and "I can write it cold" is bigger than most people expect. Spaced repetition closes that gap. You revisit the coin change DP table at increasing intervals, write the recurrence from scratch each time, and after a few reps the pattern is second nature.

The linear DP with constant state pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - The gentlest intro to dynamic programming, same building block with a simpler transition
• Jump Game - Another problem where you build up a DP/greedy solution by considering what you can reach from each position
• Best Time to Buy and Sell Stock - A single-pass DP problem that tracks a running optimum, showing the same "build from smaller subproblems" idea