Coin Change

The idea

Given coin denominations and a target amount, I want the fewest coins that sum to it. Greedy fails here: with coins [1, 3, 4] and amount 6, taking the biggest coin first gives 4 + 1 + 1 (three coins) when 3 + 3 (two coins) is better. The choice at each step depends on what is still left to make, so this is a DP.

I define dp[a] as the minimum number of coins that add up to a. The answer I want is dp[amount].

Brute force, then the optimization

The recursive brute force tries 1 + min(coins(a - c)) over all coins c. It re-solves the same subamounts repeatedly, which is exponential.

Since coins repeat freely, this is an unbounded-knapsack DP. I build dp from 0 up to amount. For each amount a, I look back at the already-solved a - coin and ask if that subproblem plus one more coin beats my current best. I seed dp[0] = 0 and everything else with a sentinel meaning "unreachable."

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1  # more coins than any real answer could need
    dp: list[int] = [0] + [INF] * amount
 
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
 
    return dp[amount] if dp[amount] != INF else -1

Correctness and complexity

dp[a] is only ever set from a strictly smaller, already-final dp[a - coin], so each entry is correct by the time I read it. Using amount + 1 as the sentinel is safe: a real answer never needs more than amount coins, so an entry left at INF truly cannot be formed, and I return -1. The two nested loops give O(amount * len(coins)) time and O(amount) space.