322. Coin Change

Coin Change is the problem that breaks your faith in greedy. Grabbing the biggest coin that fits feels right, and for real-world currencies it usually works — but the interviewer hands you a coin set where it quietly gives the wrong count. The fix is dynamic programming, and this is one of the cleaner members of the DP pattern family.

The problem

You get a list of coin denominations (unlimited supply of each) and a target amount. Return the fewest coins that add up exactly to amount, or -1 if no combination works. (Full statement on LeetCode.)

With coins = [1, 3, 4] and amount = 6, the answer is 2 — two 3s. Hold onto that case; it’s about to matter.

Intuition: why greedy fails and DP doesn’t

The tempting move is greedy: keep taking the largest coin that still fits. On [1, 3, 4] for 6, greedy grabs 4, then can only add 1 + 1 — three coins. But 3 + 3 is two. Greedy commits to 4 too early and never reconsiders, because a locally biggest choice isn’t always part of the globally smallest set.

So you can’t decide one coin at a time in isolation. Instead, define the subproblem: let $f(a)$ be the fewest coins that make amount $a$. To make $a$, some coin is the last one you place. If that coin has value $c$, the rest of the pile must make $a - c$, and you already know the best way to do that. Try every coin as the last one and keep the smallest:

$f(a) = \min_{c \,\in\, \text{coins},\ c \le a}\ f(a - c) + 1$

with $f(0) = 0$ — zero coins make zero. Because every choice branches into a smaller, already-solved amount, there’s no early commitment: f(6) considers f(5)+1, f(3)+1, and f(2)+1, and picks the winner. That “reconsider every option” is exactly what greedy skips.

Solution

Fill a table from 0 up to amount. Seed every cell with a sentinel that means “unreachable” — amount + 1 is safe, since you can never need more than amount coins (the smallest coin is at least 1).

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[a] = fewest coins summing to a; amount + 1 stands in for "impossible"
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;                           // base case: nothing needed for 0

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a) {             // this coin can be the last one placed
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }

        // if dp[amount] never improved past the sentinel, no combination works
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Using amount + 1 as the sentinel does double duty: it’s larger than any real answer so Math.min never picks it by mistake, and the final > amount check cleanly separates “impossible” from a genuine result. Handing back dp[amount] directly would return a bogus large number for the -1 cases.

Complexity

	Time	Space
Bottom-up DP	$O(\text{amount} \times \text{coins.length})$	$O(\text{amount})$

Each of the amount cells scans every coin once, so the runtime is the product; the table itself is the only extra memory.

In an interview

Open by killing the greedy instinct out loud — walk through [1, 3, 4] making 6, show greedy returns 3 and the real answer is 2, and say “so I need DP.” That one example proves you understand why the easy approach is wrong, which is the actual test here; plenty of candidates write greedy and never notice.

The trap to name is the impossible case. coins = [2], amount = 3 can’t be made, and if you return dp[amount] without the sentinel guard you’ll hand back garbage instead of -1. Mention that amount = 0 returns 0 for free thanks to the base case.

The “build the target from smaller pieces, one choice at a time” shape is the same engine behind Word Break (can I reach the end at all?) and Decode Ways (how many ways?). Coin Change is the minimize variant of that trio; the pattern hub lines them up side by side.

References

• LeetCode 322 — Coin Change