Coin Change

How you get there

1. 1dp[a] is the fewest coins making exactly a.
2. 2For each amount, try every coin and take the best sub-result plus one.
3. 3Ascending iteration over amounts permits reuse — this is unbounded knapsack.

Solution

def coin_change(coins: list[int], amount: int) -> int:
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1
    return -1 if dp[amount] == INF else int(dp[amount])

Time

O(amount · coins)

Space

O(amount)

What goes wrong

Greedy largest-coin-first fails on denominations like [1, 3, 4] for amount 6.