Coin Change

Signal

"Fewest coins/steps to hit an exact target, unlimited use of each piece" is a min-coins-to-a-target shape — build up the answer for every amount from 0 to the target, each one reusing smaller already-solved amounts.

Approach

For each amount a from 1 up to the target, try every coin c <= a and take the best of dp[a - c] + 1 — one coin plus however many coins it took to make the remainder. dp[0] = 0 (zero coins for zero amount). If dp[target] never got set to anything finite, no combination works.

Skeleton

dp = [0] + [infinity] * target
for a in range(1, target + 1):
    for c in coins:
        if c <= a:
            dp[a] = min(dp[a], dp[a - c] + 1)
return dp[target] if dp[target] != infinity else -1

Solution

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [float("inf")] * amount

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)

    return dp[amount] if dp[amount] != float("inf") else -1

Complexity

O(amount · len(coins)) time — every amount tries every coin once. O(amount) space for the dp array.

Pitfalls

• A greedy "always take the largest coin that fits" works for canonical currency systems (like US coins) but fails on arbitrary denominations — e.g. coins [1, 3, 4] targeting 6: greedy takes 4+1+1 (3 coins), but 3+3 (2 coins) is better. This problem needs DP, not greedy.
• Initializing dp with 0 everywhere instead of infinity for unreachable amounts silently reports impossible amounts as achievable.
• The inner loop order (coins inside, amounts outside) doesn't matter for minimum count the way it does for counting combinations (Coin Change II) — don't port that ordering constraint here by habit.