Coin Change

Difficulty: Medium

Problem

You have several coin values to choose from, and you may use any value as many times as you like. Find the smallest number of coins that add up to exactly amount, or return -1 when that total cannot be formed. Grabbing the largest coin each time looks tempting, but it can fail, which is exactly where dynamic programming helps.

Example

Input: coins = [2,5,10], amount = 27
Output: 4
Explanation: 27 = 10 + 10 + 5 + 2 uses four coins. Three coins can only reach 30, 25, 22, 20 and a few other totals, never 27, so 4 is the minimum.

Brute-force approach

No separate brute-force phase: the exponential try-every-last-coin recursion IS Step 1 of the guided walkthrough, where it gets diagnosed and upgraded into the memo and then the table.

Optimal approach

Key insight: Every way to make amount a ends with some final coin c. Try each: 1 + fewest for (a − c). The minimum over all final coins is dp[a]: greedy guessing replaced by exhaustive-but-cached trying.

Build dp[a] = fewest coins making amount a exactly, from 0 up to amount. Each amount auditions every coin as its possible FINAL coin and keeps the cheapest option; ∞ marks amounts no combination has reached, and a surviving ∞ becomes -1.

Steps

Define the state: dp[a] = fewest coins that sum to a exactly (∞ = not makeable so far)
Seed dp[0] = 0, zero coins make amount zero, and every other slot ∞
For each amount a from 1 to amount, audition every coin c ≤ a as the LAST coin
Each audition costs 1 + dp[a − c]; keep the minimum across all coins
Return dp[amount], converting a surviving ∞ into -1

Time complexity: O(amount × coins) · Space complexity: O(amount)

Pseudocode

function coinChange(coins, amount):
    dp = array of size (amount + 1), filled with ∞
    dp[____] = 0                       // zero coins make amount zero
    
    for a from 1 to amount:
        for c in coins:
            if c ____ a:               // c can only be the last coin if it fits
                dp[a] = min(dp[a], 1 + dp[____])
    
    if dp[amount] is still ∞:
        return ____                    // no combination reached amount
    return dp[amount]

Hints

There's exactly one amount you can make with zero coins. Which slot gets the free 0?
An 11-coin can't be the last coin of amount 7. What comparison lets a coin audition only when it fits?
If c was the last coin added, you paid 1 coin plus the best answer for which smaller amount?
dp[amount] still ∞ means no combination ever reached it. What sentinel does the problem's contract want instead?

Complexity questions

The Step-1 recursion (no memo): how does its running time scale?

Exponential: every call fans out into one recursive call per coin, and following the 1-coin gives depth amount. Branching factor k = len(coins), depth up to amount: a call tree with up to k^amount nodes, stuffed with the same subproblems solved over and over. That repetition, not the coin math, is what the memo removes.

The table runs in O(amount × coins). Why do computer scientists call this 'pseudo-polynomial' rather than plain polynomial?

Because it scales with the VALUE of amount, not the length of its written form. Amount = 1,000,000 is 7 characters of input but a million table slots. Formal complexity is measured against input LENGTH, and writing one more digit multiplies amount's value by 10, so the work is polynomial in the value but exponential in the digit count. For interviews, O(amount × coins) is the answer; 'pseudo-polynomial' is the fine print that shows you know what it's measured against.

How much extra space does the tabulated solution use?

O(amount): one dp slot per sub-amount from 0 to amount. One array of amount + 1 numbers. Unlike House Robber, there's no two-variable squeeze: a coin c reaches back c slots, so everything up to max(coins) behind must stay alive, in practice we keep the whole array. (The memo version is also O(amount), plus recursion stack.)

Change one word, 'how MANY ways to make amount' instead of 'FEWEST coins', and what changes in the code?

min() becomes a SUM, and suddenly loop order matters: coin-loop outside counts combinations, amount-loop outside counts permutations. Counting sums its branches (like Climbing Stairs) instead of minimizing them. And a subtlety min() never noticed appears: with the amount loop outside, 5+1 and 1+5 count as two different ways (permutations); putting the coin loop outside counts them once (combinations). Just plant that flag for now: the next lessons dig into exactly this.

Check your understanding of Coin Change

What exactly does Coin Change ask for?

The fewest COINS whose values sum to amount EXACTLY, with unlimited copies of every denomination available. Count the coins themselves (5+5+1 is THREE coins, even though it uses two denominations), the sum must hit amount exactly, no overshoot allowed, and supply is unlimited: reuse any denomination as often as you like. If nothing works, return -1.

Coins {1, 5, 11}, amount 15. What does the greedy rule 'always take the biggest coin that fits' produce, and what's actually best?

Greedy: 11+1+1+1+1 = 5 coins. Optimal: 5+5+5 = 3 coins. Greedy's big first bite strands it with four 1s. Greedy grabs the 11, leaving 4, and only 1s fit into 4, so it limps home with five coins. (11+5 = 16 overshoots, so that's not even legal.) The true optimum never touches the 11: three 5s. One counterexample kills a heuristic: memorize this one.

What's the state sentence: the meaning of one table slot dp[a]?

dp[a] = the fewest coins that make amount a EXACTLY, with ∞ meaning 'no way to make a is known yet'. One slot per sub-amount, holding the best (fewest-coin) answer for it. ∞ is the honest placeholder for 'unreachable so far': it loses every min() it enters, and if it survives all the way to dp[amount], it becomes the -1.

What's the case split that defines the recurrence?

Split on the LAST coin added: it was SOME coin c ≤ a, so dp[a] = 1 + dp[a − c], minimized over every coin c. The same last-step trick as Climbing Stairs and House Robber, but instead of 2 branches there are k, one per coin that fits. Each branch says 'I was the final coin: pay 1 for me, plus the best answer for what remained.' min() arbitrates.

When does the function return -1?

When dp[amount] is still ∞ after the fill: no combination of coins sums to amount (e.g. coins = [2], amount = 3). With coins = [2] you can only ever build even totals, so dp[3] never leaves ∞. A surviving ∞ means 'no combination reached me', and the problem's contract translates that to -1 on the very last line.