Coin Change: Bottom-Up and Top-Down Dynamic Programming

Coin Change (LeetCode 322) is the canonical dynamic programming problem. It tests your ability to identify optimal substructure, choose between top-down memoization and bottom-up tabulation, and reason about state transitions. It appears at Google, Amazon, Facebook, and Microsoft interviews constantly.

Problem

Given an array of coin denominations and a target amount, find the minimum number of coins needed to make up that amount. Return -1 if it’s not possible.

coins = [1, 5, 11], amount = 15
Answer: 3 (one 11 + ... wait: 11 + 1 + 1 + 1 + 1 = 5 coins, 5 + 5 + 5 = 3 coins)

coins = [2], amount = 3
Answer: -1 (impossible)

Bottom-Up (Tabulation)

Build the solution from smaller subproblems:
dp[i] = minimum coins needed to make amount i.

def coin_change(coins: list[int], amount: int) -> int:
    """
    Bottom-up DP: build from 0 to amount.
    dp[i] = min coins to make amount i.
    Transition: dp[i] = min(dp[i - coin] + 1) for each valid coin.
    Time: O(amount * len(coins)), Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed to make amount 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

# Example walkthrough: coins=[1,5,11], amount=15
# dp[0]=0, dp[1]=1, dp[5]=1, dp[10]=2, dp[11]=1, dp[15]=3 (5+5+5)
print(coin_change([1, 5, 11], 15))  # 3
print(coin_change([2], 3))          # -1

Top-Down (Memoization)

def coin_change_memo(coins: list[int], amount: int) -> int:
    """
    Top-down DP with memoization.
    Recursive: to make amount N, pick each coin and recurse on (N - coin).
    Time: O(amount * len(coins)), Space: O(amount) for memo + recursion stack
    """
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')

        min_coins = float('inf')
        for coin in coins:
            result = dp(remaining - coin)
            if result != float('inf'):
                min_coins = min(min_coins, result + 1)
        return min_coins

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

Variant: Coin Change 2 — Number of Combinations (LeetCode 518)

How many distinct combinations of coins make up the amount?

def coin_change_2(amount: int, coins: list[int]) -> int:
    """
    Number of ways to make amount using unlimited coins.
    dp[i] = number of combinations to make amount i.
    Key: iterate coins in outer loop to avoid counting permutations.
    (If amount in outer loop, [1,2] and [2,1] would be counted separately.)
    Time: O(amount * len(coins)), Space: O(amount)
    """
    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]

print(coin_change_2(5, [1, 2, 5]))  # 4: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]

Understanding the Loop Order

The key insight for combinations vs permutations:

Coins outer, amounts inner → combinations (LeetCode 518 — order doesn’t matter)
Amounts outer, coins inner → permutations (each ordering counted separately)

Generalizing the Pattern

Coin change is an unbounded knapsack problem: unlimited use of each item, minimize/count ways to reach target weight/value. Same pattern applies to:

Perfect Squares (LeetCode 279) — squares are the “coins”
Minimum Cost for Tickets (LeetCode 983) — days are the “amount”
Word Break (LeetCode 139) — words are the “coins”, string length is the “amount”