Bottom-Up DP Beats Recursion: Solving Coin Change in O(S×n)

The problem statement fits in two sentences. You have coins of various denominations and an unlimited supply of each. Find the minimum number of coins that sum to a target amount, or return -1 if no combination works.

That simplicity is deceptive. The brute-force attempt explodes exponentially, and the fix — caching subproblems — is exactly what separates this from a pure recursion exercise. Coin Change is the canonical entry point into unbounded knapsack DP, and it's worth understanding all four angles: naïve recursion, memoized recursion, bottom-up tabulation, and BFS shortest-path framing.

Why the constraints matter before touching any code

amount <= 10^4 and coins.length <= 12. Those two numbers immediately rule out anything factorial or exponential. The brute-force recursion is O(S^n) in the worst case — with S = 10000 and n = 12 that is not even worth computing. The constraints are telling you: O(S × n) is the target, and both DP approaches hit it.

The coin values themselves can be up to 2^31 - 1, which matters for one subtle thing: in the bottom-up loop you compare coin <= i, and if coin exceeds amount entirely, that coin is simply never usable. The check handles it without special-casing.

Brute force: pure recursion

For amount r, try every coin c where c <= r, recurse on r - c, and take the minimum result plus one. The recursion bottoms out at r = 0 (return 0 — no coins needed) or goes negative (return -1 — invalid path).

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        def helper(remaining: int) -> int:
            if remaining == 0:
                return 0
            if remaining < 0:
                return -1
            min_coins = float('inf')
            for coin in coins:
                if coin <= remaining:
                    result = helper(remaining - coin)
                    if result != -1:
                        min_coins = min(min_coins, result + 1)
            return -1 if min_coins == float('inf') else min_coins
 
        return helper(amount)

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return Helper(coins, amount);
    }
 
    private int Helper(int[] coins, int remaining) {
        if (remaining == 0) return 0;
        if (remaining < 0) return -1;
        int minCoins = int.MaxValue;
        foreach (int coin in coins) {
            if (coin <= remaining) {
                int result = Helper(coins, remaining - coin);
                if (result != -1)
                    minCoins = Math.Min(minCoins, result + 1);
            }
        }
        return minCoins == int.MaxValue ? -1 : minCoins;
    }
}

The problem is visible the moment you draw the recursion tree for coins = [1, 2, 5], amount = 6. helper(3) gets called from helper(4) (via coin 1), from helper(5) (via coin 2), and from multiple other paths. The same subproblem is recomputed dozens of times. At amount = 100 this is already painful; at amount = 10000 it never finishes.

Time: O(S^n). Space: O(S) stack depth.

Memoization: fix the overlapping subproblems

The recursion tree is a DAG, not a tree — the same nodes appear repeatedly. Cache the answer at each remaining value and return immediately on a hit.

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo: dict[int, int] = {}
 
        def helper(remaining: int) -> int:
            if remaining in memo:
                return memo[remaining]
            if remaining == 0:
                return 0
            if remaining < 0:
                return -1
            min_coins = float('inf')
            for coin in coins:
                if coin <= remaining:
                    result = helper(remaining - coin)
                    if result != -1:
                        min_coins = min(min_coins, result + 1)
            memo[remaining] = -1 if min_coins == float('inf') else min_coins
            return memo[remaining]
 
        return helper(amount)

public class Solution {
    private Dictionary<int, int> _memo = new();
 
    public int CoinChange(int[] coins, int amount) {
        _memo.Clear();
        return Helper(coins, amount);
    }
 
    private int Helper(int[] coins, int remaining) {
        if (_memo.TryGetValue(remaining, out int cached)) return cached;
        if (remaining == 0) return 0;
        if (remaining < 0) return -1;
        int minCoins = int.MaxValue;
        foreach (int coin in coins) {
            if (coin <= remaining) {
                int result = Helper(coins, remaining - coin);
                if (result != -1)
                    minCoins = Math.Min(minCoins, result + 1);
            }
        }
        int finalResult = minCoins == int.MaxValue ? -1 : minCoins;
        _memo[remaining] = finalResult;
        return finalResult;
    }
}

Each distinct remaining value from 0 to amount is now computed exactly once. The recursion tree collapses from exponential to linear in S.

Time: O(S × n). Space: O(S) for the memo dictionary plus the call stack, which can reach depth S in the worst case (e.g., only coin denomination is 1).

The stack depth is the remaining pain point. With amount = 10000 and Python's default recursion limit of 1000, this actually crashes unless you bump sys.setrecursionlimit. That alone is a reason to prefer the bottom-up version in production.

Bottom-up tabulation: the version I'd actually ship

Flip the direction. Instead of starting at amount and recursing down, start at 0 and build up. Define dp[i] as the minimum number of coins needed to reach amount i. The recurrence is:

dp[i] = min(dp[i - coin] + 1)   for each coin where coin <= i and dp[i - coin] != infinity
dp[0] = 0

Let's trace coins = [1, 2, 5], amount = 11 by hand:

Initial:  dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
               [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

i=1: coin=1 -> dp[0]+1=1. dp[1]=1
     dp = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=2: coin=1 -> dp[1]+1=2; coin=2 -> dp[0]+1=1. dp[2]=1
     dp = [0, 1, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=3: coin=1 -> dp[2]+1=2; coin=2 -> dp[1]+1=2. dp[3]=2
     dp = [0, 1, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

i=4: coin=1 -> dp[3]+1=3; coin=2 -> dp[2]+1=2. dp[4]=2
i=5: coin=1 -> dp[4]+1=3; coin=2 -> dp[3]+1=3; coin=5 -> dp[0]+1=1. dp[5]=1
i=6: coin=1 -> dp[5]+1=2; coin=2 -> dp[4]+1=3; coin=5 -> dp[1]+1=2. dp[6]=2
i=7: coin=1 -> dp[6]+1=3; coin=2 -> dp[5]+1=2; coin=5 -> dp[2]+1=2. dp[7]=2
i=8: coin=5 -> dp[3]+1=3; coin=2 -> dp[6]+1=3. dp[8]=3
i=9: coin=5 -> dp[4]+1=3. dp[9]=3
i=10: coin=5 -> dp[5]+1=2. dp[10]=2
i=11: coin=1 -> dp[10]+1=3; coin=5 -> dp[6]+1=3. dp[11]=3

Answer: dp[11] = 3  (5 + 5 + 1)

class Solution:
    def coinChange(self, 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:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            foreach (int coin in coins) {
                if (coin <= i && dp[i - coin] != int.MaxValue) {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == int.MaxValue ? -1 : dp[amount];
    }
}

Notice the dp[i - coin] != int.MaxValue guard in C#. In Python, float('inf') + 1 is still float('inf') so there's no overflow risk, but in C# adding 1 to int.MaxValue wraps around to int.MinValue and corrupts the minimum calculation. Missed that the first time I wrote it.

Time: O(S × n). Space: O(S) — just the dp array, no stack overhead.

The bottom-up version is what I'd ship. No recursion limit issues, no dictionary allocation overhead, cache-friendly linear memory access, and the logic is three lines once you have the definition right.

The diagram captures the key reachability structure: dp[5] = 1 is the anchor that makes dp[10] = 2 and dp[11] = 3 both cheap. The path 0 -> 5 -> 10 -> 11 (three coins: 5+5+1) falls out naturally.

BFS: shortest path in a coin graph

There's a fourth framing that's worth knowing. Treat the problem as shortest-path in an unweighted graph: nodes are amounts 0 through amount, and there's an edge from a to a + coin for every coin. BFS on this graph from node 0 finds amount in the minimum number of hops, which equals the minimum number of coins.

from collections import deque
 
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0
        queue = deque([(0, 0)])  # (current_amount, steps)
        visited = {0}
        while queue:
            current, steps = queue.popleft()
            for coin in coins:
                nxt = current + coin
                if nxt == amount:
                    return steps + 1
                if nxt < amount and nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, steps + 1))
        return -1

The C# version isn't provided in the source, so here it is:

using System.Collections.Generic;
 
public class Solution {
    public int CoinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        var queue = new Queue<(int amount, int steps)>();
        var visited = new HashSet<int> { 0 };
        queue.Enqueue((0, 0));
        while (queue.Count > 0) {
            var (current, steps) = queue.Dequeue();
            foreach (int coin in coins) {
                int nxt = current + coin;
                if (nxt == amount) return steps + 1;
                if (nxt < amount && visited.Add(nxt))
                    queue.Enqueue((nxt, steps + 1));
            }
        }
        return -1;
    }
}

BFS guarantees correctness because it explores amounts in order of coin count, never revisiting an amount. The visited set is critical — without it, multiple paths to the same amount all get queued and the queue grows to O(S × n) entries instead of O(S).

Time: O(S × n). Space: O(S) for queue and visited set.

I'd pick BFS over DP only if someone explicitly framed this as a graph problem on a whiteboard — the mental model translates cleanly and BFS is a familiar tool. In practice the bottom-up DP is faster (array vs. hash set overhead) and uses less memory.

Edge cases

amount = 0: both BFS and bottom-up DP handle this — BFS returns 0 before touching the queue, dp[0] = 0 directly. The recursion's base case also covers it.

No valid combination (coins = [2], amount = 3): dp[1], dp[3] stay at infinity because no coin reaches them from dp[0]. The final check returns -1. BFS exhausts the queue without ever hitting 3.

Single coin that divides amount evenly (coins = [5], amount = 10): dp[5] = 1, dp[10] = 2. Correct. If it doesn't divide (coins = [5], amount = 7): dp[5] = 1, dp[6] and dp[7] stay at infinity. Returns -1.

Very large coin values that exceed amount: the coin <= i guard means those coins are simply never consulted. No index-out-of-bounds risk.

Approach comparison

The unbounded knapsack pattern

Coin Change is the minimum-cost variant of the unbounded knapsack problem. The "unbounded" part means each item (coin) can be used any number of times — which is why the inner loop over coins happens inside the outer loop over amounts rather than the other way around, and why dp[i - coin] refers back into the same dp array being filled rather than a previous row.

The same pattern appears in LeetCode 518 (Coin Change II), which asks for the count of distinct ways instead of the minimum — the recurrence changes from min(...) to sum, but the structure is identical. LeetCode 279 (Perfect Squares) is the same problem with coins replaced by {1, 4, 9, 16, ...}. LeetCode 377 (Combination Sum IV) counts ordered ways to reach a target — the order of the loops matters there and the result is a count rather than a minimum. LeetCode 983 (Minimum Cost For Tickets) adds time-indexed state but the bottom-up table thinking transfers directly.

If you can write the recurrence dp[i] = min(dp[i], dp[i - c] + 1) for c in items from memory, you can solve all four.