Coin Change

Greedily grabbing the largest coin first does not always work (e.g. coins [1,6,7,9,11], amount 13 – greedy picks 11+1+1 but 6+7 is better), so this needs real search. Define dp[i] as the fewest coins needed to make amount i. To make i, the last coin used was some c in coins, and the rest of the amount, i - c, was made optimally by dp[i-c] coins. Trying every possible last coin and taking the best gives dp[i] = 1 + min(dp[i-c] for c in coins if c <= i).

Top-Down Memoization

Time O(amount · coins)Space O(amount)

Recurse on the remaining amount: solve(rem) is the fewest coins to make rem, trying every coin as the “next” (really: last) coin used.

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo = {}
        def solve(rem: int) -> int:
            if rem == 0:
                return 0
            if rem < 0:
                return float('inf')
            if rem in memo:
                return memo[rem]
            best = min((1 + solve(rem - c) for c in coins), default=float('inf'))
            memo[rem] = best
            return best
        result = solve(amount)
        return result if result != float('inf') else -1

Without memoization, each call branches into len(coins) more calls down to depth amount, giving an exponential blow-up. Memoizing collapses this to amount distinct subproblems, each doing O(coins) work → O(amount · coins) time, O(amount) space for the memo and recursion stack.

Bottom-Up DP

OptimalTime O(amount · coins)Space O(amount)

Fill dp[0..amount] left to right. dp[0] = 0 (zero coins needed for zero amount). For each i, try every coin c <= i as the last coin used, and take the minimum of dp[i-c] + 1. Cells that stay unreachable represent amounts that cannot be made.

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        INF = float('inf')
        dp = [0] + [INF] * amount
        for i in range(1, amount + 1):
            for c in coins:
                if i - c >= 0:
                    dp[i] = min(dp[i], dp[i - c] + 1)
        return dp[amount] if dp[amount] != INF else -1

Trace coins = [1, 2, 5], amount = 11. Watch the inner loop: for each amount i every coin is tried as the last coin, reading one earlier cell dp[i - c], and the cheapest candidate wins.

Fewest coins to make each amount

Base case

c = 1coin larger than amount — skipped—

c = 2coin larger than amount — skipped—

c = 5coin larger than amount — skipped—

dp[0] = 0: zero coins for zero amount

1 / 12

comparingseenresult

Base case: dp[0] = 0, because making amount 0 needs no coins. Every later cell is built from this one.

For each of the amount cells, every coin is tried once → O(amount · coins) time. The dp array costs O(amount) space. This is optimal in the sense that any correct DP must consider every reachable amount up to the target.

Top-Down Memoization

Bottom-Up DP

More 1-D DP practice