Coin Change

Breadth-first search — explore by coin count

Breadth-first search (BFS) explores every position one step away before taking a second step. Here a position is a reachable total, and one step means adding one coin. Start from 0; the first time you reach amount, the BFS level is the minimum coin count.

from collections import deque
 
 
def coin_change(coins: list[int], amount: int) -> int:
    queue = deque([(0, 0)])
    seen = {0}
 
    while queue:
        total, used = queue.popleft()
        if total == amount:
            return used
        for coin in coins:
            next_total = total + coin
            if next_total <= amount and next_total not in seen:
                seen.add(next_total)
                queue.append((next_total, used + 1))
    return -1

There are at most amount + 1 useful totals, and each one tries k = len(coins) denominations. Time O(amount · k). Space O(amount) for the queue and visited set.

Bottom-up min-coins DP — solve every smaller total once

Dynamic programming (DP) records answers to smaller totals so a larger total can reuse them. Let dp[a] be the fewest coins that make a. The base case is dp[0] = 0. For every coin that fits, the transition — the rule for building a new DP answer — is:

dp[a] = min(dp[a], dp[a - coin] + 1)

def coin_change(coins: list[int], amount: int) -> int:
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)
    dp[0] = 0
 
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                dp[current] = min(dp[current], dp[current - coin] + 1)
 
    return -1 if dp[amount] == unreachable else dp[amount]

amount + 1 is a safe marker because no valid minimum can use more than amount coins: even that upper bound needs denomination 1. An entry that keeps the marker is unreachable.

Time O(amount · k). Space O(amount) for the DP array.