LeetCode 322 · Medium · 1-D Dynamic Programming

Coin Change

With unlimited coins of each value in coins, return the fewest coins that add up to amount, or -1 if no mix of coins hits it exactly.

O(amount · coins)time
O(amount)space
last coindecides each amount

coins: 1–4 distinct values, 1 to 25 · amount: 0 to 24

coins each coin's candidate for the current amount: 1 + dp[a − c]

dp dp[a] = fewest coins that make a · ∞ = amount + 1, the "not reachable" sentinel

public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int a = 1; a <= amount; a++) { for (int c : coins) { if (a - c >= 0) { dp[a] = Math.min(dp[a], 1 + dp[a - c]); } } } return dp[amount] != amount + 1 ? dp[amount] : -1;}
a
—
c
—
1 + dp[a − c]
—
dp[a]
—

Why it works

  1. Brute force tries every coin at every step: recursing on amount − c for each coin explores a tree about coinsamount wide. Greedy (biggest coin first) is fast but wrong: for [1,3,4] and 6 it picks 4 + 1 + 1, while 3 + 3 uses two coins.
  2. The last coin decides: an optimal pile for a ends with some coin c, and the rest is an optimal pile for a − c. So dp[a] = 1 + min over coins of dp[a − c]. Each arc into a cell is one coin's candidate.
  3. Fill amounts upward: every a − c is smaller than a, so it is final when read. amount cells times coins.length checks: O(amount · coins) time, O(amount) space.
  4. Pitfall: the sentinel. amount + 1 works as infinity because no answer can use more than amount coins (the smallest coin is 1). Do not use Integer.MAX_VALUE instead: 1 + dp[a − c] then overflows to a negative number that wins the Math.min. An unreachable dp[amount] must turn into -1.
  5. Which coins? Walk back from amount: any coin with dp[a − c] = dp[a] − 1 was a valid last coin. The banner lists one such pile.
  6. Related: Coin Change II counts the combinations instead (loop coins outside, amounts inside). This is an unbounded knapsack; BFS over amounts gives the same answer.