LeetCode Coin Change: Bottom-Up DP Explained

LeetCode 322, Coin Change, is the textbook example of unbounded knapsack expressed in a friendly way. It is also one of the most common “medium that interviewers expect Easy fluency on” problems. Master it once and you have a template for any minimum-coins, minimum-jumps, or minimum-steps DP question.

The Problem

You are given an integer array coins of distinct positive denominations and an integer amount. Return the minimum number of coins needed to make up amount. You may use each coin an unlimited number of times. If it is impossible to make the amount, return -1.

Example inputs and outputs:

Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Input:  coins = [2], amount = 3
Output: -1
Explanation: No combination of 2s makes 3.

Input:  coins = [1], amount = 0
Output: 0
Explanation: Zero coins for amount 0.

A common trap: greedy “use the largest coin first” works for the US currency system but fails in general. For coins = [1, 3, 4] and amount = 6, greedy gives 4 + 1 + 1 = 3 coins while the optimum is 3 + 3 = 2 coins. That counterexample is worth memorizing.

Brute Force

Recurse on the remaining amount: for each coin, subtract it and recurse, taking the minimum.

def coin_change(coins: list[int], amount: int) -> int:
    def helper(remaining: int) -> int:
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return 1 + min(helper(remaining - c) for c in coins)
    result = helper(amount)
    return result if result != float('inf') else -1

Without memoization this is exponential: roughly O(k^amount) where k is the number of coin denominations. It times out almost immediately past amount = 30.

Optimal Solution

The state space is small: only amount + 1 distinct values of remaining. Tabulate bottom-up.

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for total in range(1, amount + 1):
        for c in coins:
            if c <= total:
                dp[total] = min(dp[total], dp[total - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

We use amount + 1 as the sentinel for “unreachable” because it is strictly greater than any valid answer (you can never need more than amount coins). This avoids the awkwardness of float('inf') and integer overflow concerns in other languages.

The recurrence is dp[total] = 1 + min(dp[total - c]) over all coins c that fit. We add 1 because using coin c counts as one coin on top of however many it took to make total - c.

Walk Through an Example

Take coins = [1, 2, 5], amount = 11. Build the table left to right:

dp[0]  = 0
dp[1]  = dp[0] + 1 = 1                      (use 1)
dp[2]  = min(dp[1]+1, dp[0]+1) = 1          (use 2)
dp[3]  = min(dp[2]+1, dp[1]+1) = 2          (2+1)
dp[4]  = min(dp[3]+1, dp[2]+1) = 2          (2+2)
dp[5]  = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1 (use 5)
dp[6]  = min(dp[5]+1, dp[4]+1, dp[1]+1) = 2 (5+1)
dp[7]  = 2  (5+2)
dp[8]  = 3  (5+2+1)
dp[9]  = 3  (5+2+2)
dp[10] = 2  (5+5)
dp[11] = 3  (5+5+1)

Final answer: 3. The table records the optimum for every subamount along the way, which is part of why DP is so reusable.

Edge Cases

• amount = 0: return 0. The base case dp[0] = 0 handles this naturally.
• No combination reaches the amount: return -1. The sentinel check catches this.
• A single coin equal to the amount: return 1.
• A single coin larger than the amount, with no smaller denomination: return -1.
• Duplicate coins: not allowed by constraints, but the algorithm is robust to them.
• Large amount and small coins: time is O(amount * len(coins)), still very fast.

Complexity Analysis

• Time: O(amount * k) where k = len(coins). We fill amount + 1 cells and do k work per cell.
• Space: O(amount) for the DP table.

The brute force without memoization is exponential, roughly O(k^amount). With memoization it becomes O(amount * k) time and O(amount) space, equivalent to the bottom-up version. For more on these growth rates, see /blog/big-o-notation-explained.

How to Explain It in an Interview

Walk through the problem like this:

1. Reject greedy with the [1, 3, 4] counterexample. This shows you understand why DP is necessary.
2. Define the state: dp[total] is the minimum coins to make total.
3. State the recurrence: dp[total] = 1 + min(dp[total - c]) over all coins c <= total.
4. Pick the sentinel amount + 1 and explain why it is safe.
5. Code bottom-up because it avoids stack depth and is simpler to reason about.
6. Trace one small example, then state the final time and space complexity.

Bonus points if you mention that the same recurrence solves “minimum jumps”, “minimum number of squares summing to n”, and other minimization problems. That generalization is the real takeaway.

Related Problems

• Coin Change II (LeetCode 518): count the number of combinations rather than minimize coins.
• Perfect Squares (LeetCode 279): minimum count of perfect squares summing to n; same recurrence.
• Minimum Number of Refueling Stops (LeetCode 871): another min-count DP.
• Jump Game II (LeetCode 45): minimum jumps to reach the end.
• See more minimization patterns in /blog/dynamic-programming-classic-problems.

Wrap up

Coin Change is one of the highest-leverage DP problems to internalize. The unbounded-knapsack recurrence shows up constantly, and the sentinel trick generalizes to many minimization questions. Build the bottom-up version from memory, trace it on [1, 2, 5] and [1, 3, 4], then move on to /blog/dynamic-programming-classic-problems for harder variants. The pattern is more important than the problem.