coin-change

Difficulty: Medium  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/coin-change/start

The story

A point-of-sale terminal at an Amazon Fresh checkout needs to dispense change for an exact amount, using denominations stocked in the till. Some denominations are missing (the 2-rupee coin tray is empty). The till is asked: what is the minimum number of coins the cashier can hand over to make exactly the change due? If no combination of available denominations sums to the change, alert the manager.

That count is coin-change. The same problem appears in inventory replenishment (minimum SKU bundles to fill a unit count on Amazon Supply Chain), in API quota top-ups (minimum credit packs to satisfy a per-minute quota on Stripe metered billing), in postage stamp combinations at FedEx, in DNS record lookup batching at Cloudflare, and in the canonical unbounded-knapsack family of optimisation problems across every operations research textbook.

Most importantly, it is the textbook non-canonical coin system problem: the seductive greedy works for Indian and US currency but fails on adversarial denominations. That failure is the entire lesson.

What's actually being asked

You have n coin denominations and a target amount. Each denomination may be used any number of times (including zero; this is "unbounded"). Return the minimum number of coins needed to make exactly amount, or -1 if no combination works.

Examples:

• coins = [1, 2, 5], amount = 11 → 3. 11 = 5 + 5 + 1.
• coins = [2], amount = 3 → -1. No combination of 2s sums to 3.
• coins = [1], amount = 0 → 0. Zero amount, zero coins.
• coins = [1, 3, 4], amount = 6 → 2. 6 = 3 + 3. Greedy ("take biggest first") would pick 4 + 1 + 1 = 3 coins, missing the optimum.

The non-canonical case [1, 3, 4] is the punchline: greedy is wrong, DP is required.

The naive approach

Recursion on every coin:

def f(a, coins):
    if a == 0: return 0
    if a < 0: return float('inf')
    return 1 + min(f(a - c, coins) for c in coins)

The search tree has up to n^a paths. For n = 12, amount = 25 that is roughly 10²⁷ operations. The same subproblems are recomputed exponentially. Without memoisation this is hopeless.

The key insight

This is unbounded knapsack. The resource is amount; the items are coin denominations with no quantity limit. Define dp[a] as the minimum coins to make exactly a. The last coin you placed was some c from the set; before placing it you had reached a - c with dp[a - c] coins. So:

# Unbounded knapsack recurrence:
# dp[a] = minimum coins to make exactly a
# dp[0] = 0
# dp[a] = 1 + min over c in coins of dp[a - c]   (skip terms where c > a or dp[a-c] is sentinel)
# Answer = dp[amount] if reachable, else -1

Why "unbounded"? Because when you place a coin of denomination c, the new subproblem a - c still allows all denominations including c again. Each iteration's dp[a - c] may itself have already used c. Contrast with the "0/1 knapsack" family where each item is used at most once.

The four DP questions:

1. State: dp[a] = minimum number of coins needed to make exactly amount a.
2. Base case: dp[0] = 0. Zero amount needs zero coins.
3. Transition: dp[a] = 1 + min(dp[a - c] for c in coins if c <= a and dp[a - c] is reachable). Equivalent: for each coin c, attempt dp[a] = min(dp[a], dp[a - c] + 1).
4. Answer: dp[amount] if it remained below the unreachable sentinel; else -1.

Step-by-step approach

Use a sentinel amount + 1 for "unreachable". It is strictly larger than any reachable answer (which is at most amount 1-rupee coins), so a plain min resolves "unreachable vs reachable" without branching.

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

Total work O(amount * n). For amount = 10⁴, n = 12, that is 1.2 * 10⁵ iterations, instantaneous.

A common idiomatic Python form is the inner loop reversed (iterate over coins outer, amounts inner). Both are correct here because of unbounded reuse.

Worked example

coins = [1, 3, 4], amount = 6

Return 2. Verified. The greedy "take largest first" would have given 4 + 1 + 1 = 3. The DP catches 3 + 3.

Complexity

• Time: O(amount * n) where n is the number of denominations.
• Space: O(amount) for the dp array.

At amount = 10⁴ and n = 12, that is ~10⁵ operations: bounded and fast.

Common pitfalls

• The seductive greedy: "always take the largest coin that fits". Wrong on non-canonical systems. Always state the counterexample ([1, 3, 4], target 6, greedy = 3 coins, optimum = 2) before reaching for a greedy here. Canadian, Indian, and US currencies are canonical, which is why intuition betrays you: most real-world inputs hide the bug.
• Wrong sentinel: using float('inf') works in Python but int.MAX in Java overflows on dp[a-c] + 1. Use amount + 1 as a safer sentinel.
• Forgetting c <= a: indexing dp[a - c] with negative a - c either errors (Java) or wraps (Python, indexing from the end). Always guard if c <= a.
• Initialising dp[0] wrong: dp[0] = 0, not INF. Zero amount needs zero coins; if you set it to the sentinel, every subsequent dp[a] becomes unreachable.
• Recursing without memoisation: the recursion is elegant and correct but exponential. Add @functools.lru_cache(None) and it becomes the top-down equivalent; never ship the unmemoised form.
• Using min-coin DP for "number of ways": a different DP (the count version) has the loop order flipped: outer over coins, inner over amounts, with dp[a] += dp[a - c]. Mixing the two is the most common DP confusion in this family.

Where this shows up in the enterprise

• Amazon Supply Chain replenishment: minimum SKU bundles (each bundle has a fixed unit count) to satisfy a target inventory level. Direct unbounded knapsack.
• Stripe metered billing top-ups: minimum credit-pack purchases to satisfy a quota; same DP.
• PagerDuty service-credit packs: minimum credit blocks to refund a customer for an outage of a given duration.
• FedEx postage combinations: minimum stamps to make exact postage from a stamp inventory.
• Cloudflare DNS lookup batching: minimum batch-size selections from a set of allowed batch sizes to cover a query load.
• NLP tokenisation cost (HuggingFace BPE in low-resource modes): minimum merges to express a substring given a vocabulary; structurally the same.
• Resource scheduling at Uber: minimum shift blocks (each fixed length) to cover a demand window; unbounded knapsack on the time axis.

The pattern is universal whenever items are unlimited, you optimise a count, and the resource axis is a single dimension.

Variants you'll see elsewhere

• coin-change-ii: count the number of distinct combinations that make amount (loop order matters: coins outer, amount inner). The most common follow-up.
• perfect-squares: same DP with coins = [1, 4, 9, 16, ...] up to amount.
• combination-sum-iv: count permutations that sum to target (loop order: amount outer, coins inner, opposite of coin-change-ii).
• minimum-number-of-refueling-stops: same shape on a continuous axis; greedy with a heap works because the items are sorted.
• 0/1-knapsack: limited copies of each item; outer loop on items, inner loop runs backwards over capacity to enforce single use.

The unbounded-knapsack family is one of the four canonical DP archetypes; once you have this article in your fingers, the rest are template substitutions.

How parikshan turns this into a learning loop

coin-change is the textbook "DP beats greedy" lesson and the gateway to the knapsack family.

1. Read this article, state the counterexample ([1, 3, 4], target 6) aloud, and state the recurrence before writing code: dp[a] = 1 + min(dp[a - c] for c in coins if c <= a), dp[0] = 0.
2. Practice mode with no AI: write the bottom-up O(amount * n) DP. Verify on [1, 3, 4], 6 → 2 by hand. Submit.
3. AI training: Explain the difference between this and coin-change-ii (the count version). The good explanation mentions loop order; the mediocre one waves at "different DP". Loop order is the canonical interview discriminator.
4. AI training: Find Bugs. If you wrote a greedy by accident, paste it into the assistant on input [1, 3, 4], 6. The assistant should point at the non-canonical failure mode.
5. Exam mode: redo cold. The bank's adversarial test includes [2], 3 → -1, [1], 100 → 100, [4, 6, 8], 7 → -1, and [1, 3, 4], 6 → 2. All four must pass; any one failure points at a specific bug class.

In the AI-integrated workspace

This problem is the second-most-common DP brain-teaser an AI agent gets wrong (after maximum-product-subarray). Three failure modes dominate:

• The greedy ship: an agent produces "sort coins descending, take greedily, repeat". Passes US/Indian denominations; fails the bank's [1, 3, 4], 6 test. The most insidious failure because sample tests with canonical coins miss the bug.
• The unmemoised recursion ship: an agent writes the recurrence as a recursive function without @lru_cache. Passes small inputs; TLEs on amount = 10⁴.
• The wrong-loop-order ship: an agent confuses min-coins with count-combinations and ships the wrong loop order. The output is structurally similar but numerically wrong on every input.

The 2027 engineer's discipline:

1. State the counterexample to greedy in your own words before generating code. If the agent proposes greedy, push back with [1, 3, 4].
2. State the recurrence in English and pin it: dp[a] = 1 + min(dp[a - c]) for valid c, dp[0] = 0. Tell the agent to implement that recurrence.
3. Verify on [1, 3, 4], 6. The answer must be 2. Greedy returns 3; if the agent's code returns 3, it shipped greedy. Reject.
4. Verify on [2], 3. The answer must be -1. Tests sentinel handling.
5. Demand the sentinel amount + 1, not float('inf'). The sentinel choice matters when porting the solution to Java or Go where integer overflow is real.
6. Watch the loop order if the conversation shifts to count-combinations. The agent will silently keep the min-coins loop order on a count-combinations problem; the bug shows up as numerically wrong outputs (often off by factors).

A candidate who can articulate "DP, unbounded knapsack, sentinel = amount + 1, watch loop order" in seven seconds is the engineer who directs AI to a correct ten-line solution. Without that articulation, the agent ships code that compiles, almost works, and fails in production on every non-canonical input.