LeetCode 322 Coin Change: From Recursion to Memoization to Bottom-Up DP

Coin Change is the problem most people use to learn dynamic programming, and it's still a regular in interviews because it tests the whole DP process in miniature: rejecting a tempting greedy, defining a state, writing a recurrence, choosing an iteration order and handling the impossible case. If you can explain each of those steps for Coin Change, you can apply them to problems you've never seen.

This guide follows that process in order, from plain recursion to memoization to tabulation, with a full table you can check by hand. Then it covers the counting version (Coin Change II) and the loop-order rule that trips up even experienced candidates. For the broader family this belongs to, see knapsack DP patterns.

The Problem: Fewest Coins to Make an Amount

You're given an array coins of distinct denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If it can't be made, return −1. You have an unlimited supply of each coin.

Constraints: 1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2³¹ − 1, 0 ≤ amount ≤ 10⁴. Two details matter. Coins can be huge (bigger than the amount), so check c ≤ a before indexing. And amount = 0 is valid input with answer 0, not −1.

Why Greedy Fails for Coin Change

The intuitive algorithm is the one a shopkeeper uses: take the largest coin that fits, repeat. For Indian currency it works. The 1-2-5 pattern of rupee denominations (1, 2, 5, 10, 20, 50, 100, 200, 500) is what's called a canonical coin system, one where greedy is always optimal. That's exactly why it feels right.

But the problem allows any denominations, and two kinds of failure appear:

• Suboptimal answer. Coins [1, 3, 4], amount 6. Greedy: 4, then 1, then 1 = 3 coins. Optimal: 3 + 3 = 2 coins. Taking the 4 first looked good locally but left a remainder (2) that the system handles badly.
• No answer at all. Coins [2, 5], amount 6. Greedy takes 5 and is left with 1, which can't be made. Yet 2 + 2 + 2 works. Greedy would wrongly return −1.

The general lesson: greedy is correct only when you can prove an exchange argument (that swapping the greedy choice into any optimal solution keeps it optimal). For arbitrary coin sets, no such proof exists. The greedy algorithms guide shows how to tell the difference. In an interview, giving the [1, 3, 4] counterexample in the first two minutes is the cleanest way to justify reaching for DP.

Step 1: The Recursive Formulation

The trick to most DP problems is asking one question about the last decision. Here: in an optimal way to make amount a, what was the last coin added?

It was one of the coins, say c. Whatever came before it must be an optimal way to make a − c (if it weren't, swapping in a better one would improve the total). We don't know which c it was, so try all of them and keep the best:

def coin_change_recursive(coins, amount):
    def solve(a):
        if a == 0:
            return 0
        best = float('inf')
        for c in coins:
            if c <= a:
                best = min(best, 1 + solve(a - c))
        return best

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

This is correct but exponential. With coins [1, 2, 5] and amount 11, solve(11) calls solve(10), solve(9) and solve(6); solve(10) calls solve(9) again, and so on. The same subproblems are solved over and over:

Those repeated nodes are the "overlapping subproblems". There are only amount + 1 distinct subproblems (0 to amount), but the tree has exponentially many nodes. Caching fixes that.

Step 2: Memoization (Top-Down DP)

Store each solve(a) the first time you compute it. Now each of the amount + 1 states is computed once, and each computation loops over n coins: O(amount × n) time.

from functools import lru_cache
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @lru_cache(maxsize=None)
        def solve(a: int) -> float:
            if a == 0:
                return 0
            best = float('inf')
            for c in coins:
                if c <= a:
                    best = min(best, 1 + solve(a - c))
            return best

        ans = solve(amount)
        return -1 if ans == float('inf') else int(ans)

One practical issue: recursion depth. With coin 1 and amount 10,000, the chain solve(10000) → solve(9999) → … goes 10,000 calls deep. Python's default limit is about 1,000, so this raises RecursionError unless you raise the limit. Java and C++ usually cope at this size, but it's a real risk for larger amounts. That's the main practical reason to convert to bottom-up.

Step 3: Bottom-Up DP (Tabulation)

The recurrence for dp[a] only depends on smaller amounts, so fill the table from 0 upward. By the time you compute dp[a], every dp[a − c] is ready.

1. State: dp[a] = fewest coins to make amount a.
2. Base case: dp[0] = 0.
3. Initial value: every other entry = amount + 1, an impossible count (you never need more than amount coins, since every coin is ≥ 1).
4. Transition: for each a from 1 to amount and each coin c ≤ a: dp[a] = min(dp[a], dp[a − c] + 1).
5. Answer: dp[amount] if it's ≤ amount, else −1.

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1
        dp = [0] + [INF] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] <= amount else -1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int INF = amount + 1;
        vector<int> dp(amount + 1, INF);
        dp[0] = 0;
        for (int a = 1; a <= amount; ++a) {
            for (int c : coins) {
                if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Why amount + 1 instead of Integer.MAX_VALUE

If you initialise with Integer.MAX_VALUE or INT_MAX, then dp[a − c] + 1 overflows to a large negative number for an unreachable a − c, and min happily picks it. The answer becomes garbage. amount + 1 is safely "infinite" for this problem and can't overflow. In Python this doesn't matter, but writing it the same way in every language is a good habit.

The coin-outer version

You can also loop over coins outside and amounts inside. The meaning of the table shifts slightly: after processing the first k coins, dp[a] is the fewest coins to make a using only those k denominations. Adding coin k+1 either isn't used (keep the old value) or is used at least once (one copy plus the best way to make a − c with the first k+1 coins, which is already computed because we go upward). After the last coin, dp[a] allows every denomination, so the answer is identical. This version is the one that generalises to counting, which is why it's worth knowing.

def coin_change_coin_outer(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):       # upward: coin c can be reused
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] <= amount else -1

Starting the inner loop at c removes the c ≤ a check. Going upward is what allows unlimited copies of the coin: when we compute dp[a], dp[a − c] may already include coin c. If each coin could be used only once (0/1 knapsack), you'd iterate downward instead.

Complexity

"Pseudo-polynomial" is worth knowing as a term: the running time grows with the value of amount, which is exponential in the number of digits used to write it. If amount were 10¹⁸, this DP would be hopeless. The general problem (with arbitrary amount) is NP-hard, which is why no truly polynomial algorithm is expected.

DP Table Dry Run: coins = [1, 2, 5], amount = 11

Each cell shows the candidates dp[a − c] + 1 for c = 1, 2, 5 and the minimum chosen.

dp[11] = 3. Check one row by hand: for a = 9, via coin 2 we look at dp[7] = 2, so 3; via coin 5 we look at dp[4] = 2, also 3; via coin 1 we look at dp[8] = 3, so 4. Minimum 3. Being able to fill two or three rows like this on a whiteboard is the best proof to an interviewer that your recurrence is right.

Reconstructing the coins

To return the actual coins, remember which coin achieved each minimum, then walk back from amount.

def coin_change_with_coins(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    choice = [0] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                choice[a] = c
    if dp[amount] > amount:
        return None
    used, a = [], amount
    while a > 0:
        used.append(choice[a])
        a -= choice[a]
    return used

# coin_change_with_coins([1, 2, 5], 11) -> [1, 5, 5]

The BFS View: Shortest Path in an Implicit Graph

There's a second way to see this problem. Treat each amount from 0 to amount as a node, with an edge from x to x + c for each coin. The fewest coins is then the shortest path from 0 to amount in an unweighted graph, which BFS finds level by level.

from collections import deque

def coin_change_bfs(coins, amount):
    if amount == 0:
        return 0
    seen = [False] * (amount + 1)
    seen[0] = True
    q = deque([0])
    steps = 0
    while q:
        steps += 1
        for _ in range(len(q)):              # process one level
            x = q.popleft()
            for c in coins:
                y = x + c
                if y == amount:
                    return steps
                if y < amount and not seen[y]:
                    seen[y] = True
                    q.append(y)
    return -1

Same worst-case complexity, O(amount × n), but BFS can stop early as soon as it reaches the target, which helps when the answer uses few large coins. It's also a nice thing to mention because it shows you see the connection between DP on a DAG and shortest paths; the BFS and DFS guide covers the level-by-level pattern used here.

Coin Change II (LeetCode 518) and the Loop-Order Rule

Coin Change II asks a different question about the same input: how many combinations of coins make up the amount? Order doesn't matter, so 1 + 2 and 2 + 1 count once.

The state becomes ways[a] = number of combinations making a, with ways[0] = 1 (one way to make zero: take nothing). The transition replaces min with a sum. And the loop order now matters.

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        ways = [1] + [0] * amount
        for c in coins:                       # coins OUTSIDE: combinations
            for a in range(c, amount + 1):
                ways[a] += ways[a - c]
        return ways[amount]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 64-bit table: the problem guarantees only the final answer fits in 32 bits
        vector<unsigned long long> ways(amount + 1, 0);
        ways[0] = 1;
        for (int c : coins)
            for (int a = c; a <= amount; ++a)
                ways[a] += ways[a - c];
        return static_cast<int>(ways[amount]);
    }
};

Why coins must be the outer loop

With coins outside, you first count every way to use only coin 1, then extend those counts to allow coin 2, and so on. Each combination is built in one fixed order (all 1s, then all 2s, then all 5s), so it's counted exactly once.

With amounts outside and coins inside, ways[a] sums over "the last coin is c" for every c, so 1 + 2 (last coin 2) and 2 + 1 (last coin 1) are counted separately. That computes the number of ordered sequences, which is a different problem: LeetCode 377, Combination Sum IV.

Dry run: coins [1, 2, 5], amount 5

Answer 4: {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}. On the C++ version: LeetCode guarantees the final answer fits in a signed 32-bit integer, but entries for smaller amounts aren't covered by that promise, so a 64-bit (or unsigned) table avoids overflow surprises in intermediate values.

For the minimum-coins problem, the loop order doesn't matter because min doesn't care how many times a combination is "seen". This min-versus-count distinction is one of the most useful things to internalise from this problem. The DP interview questions guide lists more problems where it applies.

How Coin Change Shows Up in Interviews

Coin Change is commonly reported at Amazon, Microsoft, Goldman Sachs, and Indian fintech and product companies (it naturally fits a payments context like UPI or wallets). It's usually a medium-level DP check. What interviewers look for:

• Rejecting greedy with a counterexample, not a vague "greedy might not work".
• A clearly defined state: "dp[a] is the minimum coins for amount a", said before any code.
• The recurrence derived from the last choice, plus base case and impossible marker.
• Iteration order justified: smaller amounts are computed first.
• Complexity stated as O(amount × n), ideally with the word pseudo-polynomial.

Variants interviewers switch to

Follow-up questions to prepare for

• "Can you reduce space?" It's already 1D, O(amount). You can't do better in general because any amount may be needed later.
• "When is greedy correct?" For canonical coin systems, like 1-2-5 style currencies. Testing whether a system is canonical is a known problem with polynomial algorithms, but you don't need the details in an interview.
• "What if coins can be used at most once?" 0/1 knapsack: iterate amounts downward in the 1D table.
• "What if you also need the coins?" Store the choice per amount and walk back.

Common Mistakes

• Returning −1 for amount 0. The answer is 0.
• Overflow from INT_MAX + 1. Use amount + 1 as the sentinel.
• Indexing with a coin larger than the amount. Check c ≤ a, or start the inner loop at c.
• Using greedy after sorting coins. Fails [1, 3, 4] / 6 and [2, 5] / 6.
• Swapping loops in Coin Change II. Gives the Combination Sum IV answer instead.
• Memoizing with a mutable default or global cache across test cases. In Python, define the cache inside the method so each call starts fresh.
• Recursion depth with memoization. Fine in theory, crashes in Python for large amounts.

The process you used here (find the last choice, define the state, write the recurrence, pick an order) is the same one behind Longest Increasing Subsequence and Word Break. Work through those next and you'll notice the DP stops feeling like memorised tables and starts feeling like one repeatable method.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.