Coin Change

Hints

1. Kill greedy with a concrete input. Try coins = [1, 3, 4], amount = 6. Greedy takes 4, then 1, then 1, for three coins. The optimum is 3 + 3, two coins. Greedy is optimal only for canonical denomination systems, and nothing in the constraints promises one.
2. Define the state as the amount, not the coin. Let dp[a] be the fewest coins that make exactly a. One integer per amount is enough state; which coins were used does not need to be remembered, because only the count is asked for.
3. Get the base case right. dp[0] = 0: zero coins make zero. Every other cell starts at infinity, meaning "not known to be reachable". That sentinel is what lets the -1 case fall out at the end without a separate reachability pass.
4. Write the transition as a minimum over the last coin. Any solution for a ends with some coin c <= a, and the rest is a solution for a - c. So dp[a] = 1 + min(dp[a - c]) over all valid c. You are enumerating the final choice, which is the standard way to derive a DP recurrence.
5. Iterate amounts forward. Each coin may be reused without limit, so when you compute dp[a] the value dp[a - c] should already include solutions that used c. Forward iteration gives exactly that. The backward sweep you may remember from 0/1 knapsack exists to prevent reuse, which is the opposite requirement.
6. Guard against arithmetic on the sentinel. If dp[a - c] is still infinity, then dp[a - c] + 1 must not be written into the table. In Python float infinity absorbs the addition harmlessly, but with an integer sentinel such as amount + 1 it silently produces a finite wrong answer.

Solution: three approaches

Approach 1 - Bottom-up DP: O(amount * k) time, O(amount) space

The canonical answer. Fill a table of best counts from 0 upwards.

def coin_change(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0

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

    return dp[amount] if dp[amount] != INF else -1

Why the recurrence is complete: every solution for amount a uses at least one coin, and whichever coin you designate as the last one, call it c, the remainder is a solution for a - c. Taking the minimum over all c <= a therefore considers every possible solution exactly once per choice of last coin. Nothing is missed, and by optimal substructure the best remainder is already sitting in dp[a - c].

Why forward iteration permits reuse: when the loop reaches a, every smaller index is final. dp[a - c] may itself have been built using c, and that is exactly what unlimited supply means. Contrast 0/1 knapsack, where each item exists once and the sweep runs backwards precisely so that a cell cannot see an update that already consumed the same item. The direction of the loop is the entire difference between the bounded and unbounded variants, as laid out in knapsack variants.

Why it is O(amount * k): the outer loop runs amount times, the inner loop over k = len(coins) denominations, and each iteration does constant work. With the given limits that is at most 10^4 * 12 = 1.2 * 10^5 operations. Note this is pseudo-polynomial, not polynomial: the running time scales with the numeric value of the amount rather than with the number of bits used to write it down. Double the digits in the amount and the work grows by a factor of ten, which is why this technique stops being viable for very large targets.

Why the infinity guard matters: dp[a - c] stays at the sentinel when a - c is unreachable, as happens throughout coins = [2], amount = 3. Adding one to a genuine infinity and taking a minimum is harmless with floats, but many people use amount + 1 as a cheap sentinel, and then amount + 2 is a finite number that can win a min and propagate a wrong count. Either use a true infinity or keep the explicit guard.

Approach 2 - BFS over amounts: O(amount * k) time, O(amount) space

The shortest-path reading, level by level. Each level is one more coin spent.

from collections import deque

def coin_change_bfs(coins, amount):
    if amount == 0:
        return 0
    visited = {0}
    queue = deque([0])
    steps = 0
    while queue:
        steps += 1
        for _ in range(len(queue)):
            cur = queue.popleft()
            for c in coins:
                nxt = cur + c
                if nxt == amount:
                    return steps
                if nxt < amount and nxt not in visited:
                    visited.add(nxt)
                    queue.append(nxt)
    return -1

Why it is correct: every edge costs one coin, so BFS visits amounts in non-decreasing order of coin count and the first time it touches the target it has done so with the fewest possible coins. The visited set is what keeps it linear; without it the same amount is re-expanded once per path that reaches it and the queue explodes combinatorially. In practice BFS often beats the DP table on inputs where the answer is small, because it stops as soon as the target is hit rather than filling every cell up to amount. It loses when the answer is large or the amount is unreachable, since it then explores the whole space anyway with heavier per-node costs. More on choosing between traversal orders in BFS versus DFS.

Approach 3 - Top-down memoisation: O(amount * k) time, O(amount) space plus recursion

The recurrence written as it was derived, with a cache bolted on.

from functools import lru_cache

def coin_change_memo(coins, amount):
    @lru_cache(maxsize=None)
    def best(a):
        if a == 0:
            return 0
        if a < 0:
            return float('inf')
        return min((best(a - c) + 1 for c in coins), default=float('inf'))

    result = best(amount)
    return result if result != float('inf') else -1

This is the most direct transcription of "the answer for a is one more than the best answer for a minus some coin". The cache turns an exponential tree of repeated calls into one evaluation per distinct amount, giving the same asymptotic cost as the table. Two practical drawbacks: recursion depth reaches amount / min(coins), which is 10^4 frames when the smallest coin is 1 and overflows CPython's default limit; and it only evaluates amounts actually reachable from the target, which is a win on sparse inputs and a wash otherwise. Memoisation versus tabulation covers when each direction pays off.

Complexity comparison

Edge cases to verify

• Amount is zero: returns 0. The table's base case handles it; the BFS needs an explicit guard before the loop or it returns -1.
• Unreachable amount: coins = [2], amount = 3 returns -1. Every odd cell stays at the sentinel.
• A coin larger than the amount: coins = [1, 2^31 - 1], amount = 5. The c <= a guard skips it; without that guard the index goes negative and Python wraps around to the end of the list, producing a plausible wrong answer rather than a crash.
• Greedy trap: coins = [1, 3, 4], amount = 6 returns 2. Any greedy submission returns 3 here.
• Single unit coin: coins = [1], amount = 10^4 returns 10^4. This is the input that overflows the recursive version.

Where beginners go wrong

• Submitting greedy because it works on real money. Everyday denominations are canonical by design, so the habit is trained by daily life rather than by the problem. coins = [1, 3, 4], amount = 6 is the two-second refutation; have it ready before you are asked for one.
• Initialising dp[0] to infinity, or leaving it unset. Zero coins make zero. Without that base case every cell stays unreachable and the function returns -1 for every input, including ones with obvious answers.
• Adding one to the sentinel. dp[a - c] + 1 when dp[a - c] is unreachable must never be written. With float infinity it is harmless; with an integer sentinel such as amount + 1 it produces a finite value that can win a min and quietly corrupt every cell that depends on it.
• Iterating amounts backwards. The backward sweep is the 0/1 knapsack idiom and it exists to stop an item being used twice. Here reuse is the point. Reversing the loop turns this into "each coin at most once", which answers a different question and still returns plausible numbers.
• Missing the c <= a guard. Denominations can exceed 2^31 - 1 while the amount is small, so a - c goes negative. Python interprets a negative index as counting from the end of the list, so instead of an error you get a silent read from the wrong cell.
• Returning dp[amount] without translating the sentinel. The contract says -1 for unreachable, not infinity and not amount + 1. One line at the end, and it is the line reviewers most often find missing.

Interview follow-ups to expect

• "Count the number of ways to make the amount, not the minimum coins." Coin Change II. Same table, but the loops swap nesting: coins outside, amounts inside, with dp[a] += dp[a - c]. That order counts each multiset once. Putting amounts outside counts ordered sequences instead and overcounts, which is the single most instructive loop-order bug in dynamic programming.
• "Return which coins were used." Store the coin that achieved each minimum in a parallel array, then walk backwards from amount, subtracting as you go. O(amount) extra memory and it makes the answer auditable.
• "Each denomination is available only once." Now it is 0/1 knapsack: iterate coins on the outside and amounts backwards on the inside so no coin is consumed twice in the same pass.
• "Each denomination has a limited count." Bounded knapsack. Naively multiply out the copies, or use binary splitting to represent a count of m with log m pseudo-coins of sizes 1, 2, 4 and the remainder.
• "The amount is 10^9." The table no longer fits and the algorithm is pseudo-polynomial, so its running time tracks the value rather than the input size. Say that plainly, then reach for number-theoretic structure: with few denominations the Chicken McNugget theorem bounds what is unreachable, and the answer becomes largely periodic in the amount.
• "Prove greedy is safe for a given coin system." For a fixed set you can verify canonicality by checking the greedy answer against the DP answer for every amount up to a bound derived from the two largest denominations. Finite check, and a nice answer because it shows you know greedy is a property of the coins rather than of the problem.

Related reading

• Dynamic Programming: the module this belongs to, including how to derive a recurrence by enumerating the last decision.
• Knapsack Variants: why loop order and loop direction encode bounded versus unbounded supply.
• Longest Common Subsequence: the two-dimensional counterpart, where the state needs a pair of indices rather than a single amount.