SpaceComplexity

What Is the Coin Change Problem? The DP Intuition, Explained

June 5, 20268 min read
dsaalgorithmsinterview-prepdynamic-programming
What Is the Coin Change Problem? The DP Intuition, Explained
TL;DR
  • Greedy algorithms fail the coin change problem when denominations don't nest cleanly — construct a counterexample ([1,3,4], amount 6) before reaching for DP.
  • The DP recurrence is dp[i] = min(dp[i - coin] + 1) for every coin ≤ i, building bottom-up from dp[0] = 0.
  • Bottom-up tabulation solves the problem in O(amount × n) time and O(amount) space; top-down memoization produces the same complexity with a recursive frame.
  • The critical initialization bug: setting dp[0] = 1 instead of dp[0] = 0 corrupts every subsequent calculation.
  • Coin Change II (LeetCode 518) flips the loop order — coins in the outer loop, amounts inner — to count distinct combinations without double-counting orderings.
  • Reconstruction follow-up requires a choice[] array tracking which coin minimized each dp[i], then backtracking from amount to 0.

The coin change problem is where most people first realize that greedy algorithms can be completely, humiliatingly wrong while radiating total confidence. You have a pile of coins and a target amount. Pick the fewest coins to hit that target. The obvious approach fails. The correct one is a gateway to one of the most important ideas in computer science.

The Setup

You get an array of coin denominations and a target amount. Return the minimum number of coins needed to make that amount. If it's impossible, return -1.

# LeetCode 322
coins = [1, 5, 10, 25]
amount = 41
# Answer: 4 (25 + 10 + 5 + 1)

coins = [2]
amount = 3
# Answer: -1 (can't make 3 with only 2-coins)

You can use any coin as many times as you want. This is the unbounded variant. Infinite supply. Unlimited budget. Still somehow a hard problem.

Greedy: Very Confident, Very Wrong

The instinct is: always grab the biggest coin that fits. For US denominations (1, 5, 10, 25 cents), this works every single time. It also works for a lot of other common systems. So greedy gets really cocky.

Then you try this:

coins = [1, 3, 4]
amount = 6

Greedy grabs the 4 first. Feeling great. Now it needs 2 more. Only 1-coins fit. Final answer: 4 + 1 + 1 = 3 coins.

Optimal answer: 3 + 3 = 2 coins.

Greedy failed because it committed to a local choice without checking whether that choice closes off a better global path. It's the algorithm equivalent of taking the first parking spot you see and then realizing the lot was empty. The coin change problem has optimal substructure but not the greedy choice property, which is exactly why dynamic programming exists.

images/dp-vs-greedy.svg Greedy picks 4, then needs two 1s. DP finds 3+3. Same amount, one fewer coin.

What DP Actually Does Here

To find the minimum coins for amount 11, you need the minimum coins for amounts 10, 8, and 7 (assuming coins 1, 3, 4). To find those, you need even smaller amounts. The subproblems overlap. A naive recursion recomputes the same amounts dozens of times. It's busy work dressed up as progress.

The key realization: the minimum coins for amount i depends only on the minimum coins for smaller amounts.

Define dp[i] as the minimum number of coins to make amount i. The recurrence:

dp[i] = min(dp[i - coin] + 1) for each coin ≤ i
dp[0] = 0   (zero coins to make zero)
dp[i] = ∞   initially (unreachable)

For each amount i, try every coin. If you use that coin, you need dp[i - coin] more coins to cover the remainder. Take the minimum across all valid coins.

The Bottom-Up Solution

Build up from amount 0. By the time you reach amount i, every smaller amount is already solved.

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Tracing through coins = [1, 3, 4], amount = 6:

amountdp valuereasoning
00base case
11one 1-coin
22two 1-coins
31one 3-coin
41one 4-coin
524+1 or 3+1+1 (same)
623+3

At i=6, the algorithm tries each coin: dp[6-1]+1 = 3, dp[6-3]+1 = 2, dp[6-4]+1 = 3. It picks 2. No drama, no backtracking. Just methodical.

The Top-Down Solution (For Recursion People)

Some people find the recursive framing more intuitive. Start from the target and work down. Memoize to avoid recomputing.

from functools import lru_cache

def coinChange(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def dp(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return 1 + min(dp(remaining - coin) for coin in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

Both approaches produce the same answer with the same time complexity. The bottom-up version wins in interviews: no recursion depth issues, and once you're comfortable with DP it reads cleanly from top to bottom.

See memoization and tabulation for a deeper look at each approach.

Time and Space Complexity

Time: O(amount × n), where n is the number of coin denominations. For every amount from 1 to amount, you try every coin.

Space: O(amount). The dp array has amount + 1 entries. The top-down version also uses O(amount) space for the call stack and memo table.

For amount = 10,000 and 10 denominations, that's 100,000 operations. Your laptop will not notice.

One very common interview mistake: initializing dp[0] = 1 instead of dp[0] = 0. Zero coins are needed to make zero. Setting it to 1 corrupts every subsequent calculation and your code will produce wrong answers that look almost right. The worst kind of bug.

The Variant: Coin Change II

LeetCode 518 asks a different question: how many distinct combinations of coins make the target amount? Order doesn't matter (3+1 and 1+3 count as one combination).

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make 0: use no coins

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

The critical difference is loop order. In Coin Change I, amounts are in the outer loop and coins in the inner loop. In Coin Change II, you flip it: each coin in the outer loop, then amounts.

The outer-coin loop ensures each coin is considered as part of combinations without double-counting orderings. This is the unbounded vs 0/1 knapsack distinction in practice. Mixing up the loop order here is a classic source of wrong answers that pass basic test cases and fail on edge cases.

Bugs That Will Hurt You In An Interview

Bug 1: Returning 0 when amount is impossible.

# Wrong
return dp[amount]

# Correct
return dp[amount] if dp[amount] != float('inf') else -1

Bug 2: Off-by-one on the dp array size.

dp = [float('inf')] * amount misses dp[amount]. You need amount + 1 slots. Every time.

Bug 3: Forgetting the base case.

Without dp[0] = 0, every entry starts at infinity and nothing ever improves. You've built a table that's technically correct and completely useless.

Why Interviewers Love This Problem

Coin change is a filter for whether you understand DP structurally or just recognize it by shape. If you jump straight to greedy, the interviewer can probe: "Does this always work?" A strong candidate immediately constructs a counterexample. That demonstration of thinking, not the solution itself, is what earns the strong hire.

It scales well as a conversation too. After the basic solution, common follow-ups include:

  • Reconstruct the actual coins used (not just the count)
  • What if coin supply is limited? (0/1 knapsack variant)
  • Coin Change II: count distinct ways instead of minimum coins

The reconstruction follow-up is especially common. You need a separate choice array tracking which coin minimized each dp[i], then backtrack from amount to 0.

def coinChangeWithPath(coins: list[int], amount: int) -> list[int]:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    choice = [-1] * (amount + 1)

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                choice[i] = coin

    if dp[amount] == float('inf'):
        return []

    result = []
    current = amount
    while current > 0:
        result.append(choice[current])
        current -= choice[current]
    return result

For more problems in this category, top dynamic programming interview problems covers the canonical list with the same depth.

Practice the Explanation, Not Just the Code

Writing the DP table is the easy part. In an actual interview, you need to explain why greedy fails, identify the subproblem structure before touching code, and derive the recurrence out loud while someone watches you.

That verbal reasoning is where most candidates lose points, because LeetCode does not train it. If you want to practice walking through DP problems in a voice interview format, SpaceComplexity runs rubric-based mock interviews where you explain your approach as you go. Same environment, same pressure, before the real thing.

Further Reading