Coin Change: Unbounded Choices, Minimum Count

"Coin Change" shows up again and again in Amazon, Bloomberg, Meta phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Dynamic Programming pattern quickly and code it cleanly. Part 6 of 11 in the Dynamic Programming arc.

The Problem

Given coin denominations (unlimited supply) and an amount, return the fewest coins summing to it, or -1. The canonical unbounded-knapsack-style DP, and the canonical greedy-refuter: largest-coin-first fails on innocent inputs, which is usually the interview's opening trap.

Input:  coins = [1, 2, 5], amount = 11
Output: 3
5 + 5 + 1. For coins = [2], amount = 3, the answer is -1.

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Optimal count over unlimited reuse of items: dp[a], the fewest coins for amount a, with dp[a] = 1 + min(dp[a − coin]) over usable coins. Unbounded reuse is what permits the single forward array; the 0/1 variant (each item once) needs the backward iteration — that distinction is a favorite probe.

The Approach

Table of size amount + 1, seeded dp[0] = 0, infinity elsewhere. For each amount, minimize over coins that fit. Unreached infinity at the end means impossible — return -1.

Kill the greedy first: coins [1, 3, 4], amount 6 — greedy takes 4+1+1 (three coins), optimal is 3+3 (two). Then the DP is unimpeachable. BFS on amounts (each coin an edge) is an equivalent framing worth one sentence — fewest coins is shortest path.

Python Solution

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins summing to amount, else -1."""
    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])

Complexity

• Time: O(amount · coins) — each cell minimizes over all denominations
• Space: O(amount) — one 1D table

Interview Tips and Follow-Ups

• Coin Change II counts combinations — coins in the outer loop to avoid counting orderings twice. Why loop order matters there is a top-tier probe; prepare it.
• dp[0] = 0 is the load-bearing base case — it is what lets exact-fit coins terminate the recurrence.
• When amounts are astronomically large, the DP table dies — mention BFS bidirectionality or math (Frobenius-style reasoning) as directional answers.

More Dynamic Programming problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.