Problem 51 · Dynamic Programming

Coin Change

MediumClassic DSA & systems

01Problem

Given coin denominations and an amount, return the fewest coins needed to make the amount, or -1 if impossible (unlimited coins of each kind).

02Key insight

Unbounded knapsack: dp[a] = 1 + min(dp[a - c]). Greedy fails for non-canonical coin systems like [1,3,4] with amount 6.

03Solution

solution.pypython8 lines

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

Try it first.

TimeO(amount * len(coins))

SpaceO(amount)

tests.py · 4 passing

tests.pypython4 lines

assert coin_change([1,2,5], 11) == 3
assert coin_change([2], 3) == -1
assert coin_change([1], 0) == 0
assert coin_change([1,3,4], 6) == 2

04Staff-level follow-up

Amount is 10^12? The DP table is infeasible; use BFS/Dijkstra on residues mod the largest coin, or exploit structure if the coin system is canonical.