106.Coin Change

MediumBlind 751-D Dynamic Programming · 8/12

Problem

You are given coin denominations coins and a target amount. You have an unlimited supply of each coin.

Return the fewest coins whose values add up to exactly amount, or -1 if no combination works. An amount of 0 needs 0 coins.

Examples

Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Input:  coins = [2], amount = 3
Output: -1
Explanation: Only even totals are reachable.

Input:  coins = [1], amount = 0
Output: 0

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

💡 Key Insight

Greedy (largest coin first) fails — with coins = [1, 3, 4] and amount = 6, greedy gives 4 + 1 + 1 but 3 + 3 is better. Instead, think about the last coin used: if it was c, the rest is an optimal answer for amount - c. So f(a) = 1 + min over coins c <= a of f(a - c), with f(0) = 0 and f(a) = ∞ when nothing fits. There are only amount + 1 distinct subproblems, so a 1-D table of size amount + 1 filled bottom-up solves it in O(amount × coins).

Recursion (Brute Force)

TimeO(k^(amount / minCoin))SpaceO(amount / minCoin)

Intuition

To make a, try every coin as the next coin and recursively make the remainder; keep the minimum. Negative remainders are dead ends.

Recurrence: f(0) = 0; f(a) = min(1 + f(a - c)) over all c in coins with c <= a; f(a) = ∞ if no coin leads to a finite answer.

Algorithm

dfs(a): if a == 0 return 0.
best = ∞; for each c <= a: sub = dfs(a - c); if finite, best = min(best, sub + 1).
Return best; the caller maps ∞ to -1.

Visualization

coins = [1, 2, 5], amount = 5 (partial tree). f(3), f(2) and f(1) show up in several branches.

flowchart TD
    A["f(5)"] -->|"-1"| B["f(4)"]
    A -->|"-2"| C["f(3)"]
    A -->|"-5"| D["f(0) = 0"]
    B -->|"-1"| E["f(3)"]
    B -->|"-2"| F["f(2)"]
    C -->|"-1"| G["f(2)"]
    C -->|"-2"| H["f(1)"]
    E -->|"-1"| I["f(2)"]
    E -->|"-2"| J["f(1)"]
    F -->|"-2"| K["f(0) = 0"]

The -5 branch gives f(5) = 1 immediately, but plain recursion still explores every other branch in full.

Code

java

class Solution {
    private static final int INF = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        int result = dfs(coins, amount);
        return result == INF ? -1 : result;
    }

    // fewest coins to make exactly a, or INF if impossible
    private int dfs(int[] coins, int a) {
        if (a == 0) {
            return 0;
        }
        int best = INF;
        for (int c : coins) {
            if (c <= a) {
                int sub = dfs(coins, a - c);
                if (sub != INF) {
                    best = Math.min(best, sub + 1);
                }
            }
        }
        return best;
    }
}

Complexity

Time: O(k^(amount / minCoin)) — k = coins.length branches at every level, exponential.
Space: O(amount / minCoin) — recursion depth (amount when a coin of 1 exists).

Top-Down Memoization

TimeO(amount × k)SpaceO(amount)

Intuition

f(a) depends only on a. Store each result in memo[a]; there are amount + 1 states and each loops over k coins.

Algorithm

memo of size amount + 1, filled with -2 meaning "not computed" (-1 will mean "impossible").
dfs(a): a == 0 → 0; return memo[a] if computed.
Compute best as above over all coins; store best or -1.

Dry Run

coins = [1, 2, 5], amount = 11
memo[0]=0  memo[1]=1  memo[2]=1  memo[3]=2  memo[4]=2  memo[5]=1
memo[6]=2  (5+1)   memo[10]=2 (5+5)   memo[11] = 1 + min(memo[10], memo[9], memo[6]) = 1 + 2 = 3

Code

java

import java.util.Arrays;

class Solution {
    private int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, -2); // -2 = unknown, -1 = impossible
        return dfs(coins, amount);
    }

    private int dfs(int[] coins, int a) {
        if (a == 0) {
            return 0;
        }
        if (memo[a] != -2) {
            return memo[a];
        }
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            if (c <= a) {
                int sub = dfs(coins, a - c);
                if (sub != -1) {
                    best = Math.min(best, sub + 1);
                }
            }
        }
        memo[a] = best == Integer.MAX_VALUE ? -1 : best;
        return memo[a];
    }
}

Complexity

Time: O(amount × k) — each amount is solved once, trying k coins.
Space: O(amount) — memo plus recursion depth up to amount.

Bottom-Up TabulationOptimal

TimeO(amount × k)SpaceO(amount)

Intuition

Compute dp[a] for a = 1, 2, ..., amount in order. Every dp[a - c] it needs has a smaller index, so it is already final. Use amount + 1 as "infinity" — no answer can need more than amount coins (that's all 1s), and it avoids overflow when adding 1.

Algorithm

dp of size amount + 1, filled with amount + 1; dp[0] = 0.
For a = 1..amount, for each c in coins with c <= a: dp[a] = min(dp[a], dp[a - c] + 1).
Return dp[amount] > amount ? -1 : dp[amount].

Dry Run

coins = [1, 2, 5], amount = 11 (∞ = 12):

a	0	1	2	3	4	5	6	7	8	9	10	11
dp[a]	0	1	1	2	2	1	2	2	3	3	2	3

dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 1 + min(2, 3, 2) = 3.

flowchart LR
    A["dp[0] = 0"] -->|"+5"| B["dp[5] = 1"]
    B -->|"+5"| C["dp[10] = 2"]
    C -->|"+1"| D["dp[11] = 3"]

Code

java

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // acts as infinity: more coins than ever needed
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) {
                    dp[a] = Math.min(dp[a], dp[a - c] + 1); // last coin is c
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Complexity

Time: O(amount × k) — amount cells, k coins each.
Space: O(amount) — the 1-D table (already minimal for this formulation).

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(k^amount)	O(amount)
Top-Down Memoization	O(amount × k)	O(amount)
Bottom-Up Tabulation	O(amount × k)	O(amount)

Common Pitfalls

Using a greedy "biggest coin first" strategy — wrong for denominations like [1, 3, 4].
Using Integer.MAX_VALUE as infinity and then computing dp[a - c] + 1, which overflows to a negative number. Use amount + 1 or check before adding.
Forgetting amount = 0 → 0, not -1.
In memoization, conflating "not computed" with "impossible" — they need different sentinels, or impossible states get recomputed forever.
Coins can be as large as 2^31 - 1; compare c <= a before subtracting rather than computing a - c blindly.