Coin Change (LC 322)

Pattern: Unbounded Knapsack — Minimum Coins to Make Target Difficulty: Medium Key Concept: dp[a] = fewest coins to make amount a. For each amount, try every coin and take the minimum.

Problem Statement

Given integer array coins (denominations) and an integer amount, return the fewest number of coins to make amount. If impossible, return -1. You may use unlimited copies of each coin.

Example

• coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
• coins = [2], amount = 3 → -1
• coins = [1], amount = 0 → 0

---

1. Algorithm & Pseudocode

Brute force (recursion)

fewest(a):
  if a == 0: return 0
  if a < 0:  return ∞
  best = ∞
  for c in coins: best = min(best, 1 + fewest(a - c))
  return best

Optimal — Bottom-up DP

1. Let dp[0..amount] with dp[0] = 0, others = amount + 1 (sentinel — bigger than any real answer).
2. For a = 1..amount:
3. For each coin: if coin <= a, dp[a] = min(dp[a], dp[a - coin] + 1).
4. Return dp[amount] > amount ? -1 : dp[amount].

---

2. Step-by-Step Analysis

Why the recurrence works Any optimal way to make amount a ends with some coin c. Remove c: you’re left with an optimal way to make a - c. So dp[a] = 1 + min over coins c of dp[a - c].

Why bottom-up You compute small amounts first; by the time you reach a, every dp[a - c] is final.

Why sentinel amount + 1 We need a value bigger than any real answer (at most amount coins of value 1). Using Integer.MAX_VALUE would overflow on +1.

Order of loops: amount-outer, coin-inner For count of ways (LC 518), the loop order matters. For min coins here, either order works because we take a min.

ASCII Trace for coins=[1,2,5], amount=6

a:    0  1  2  3  4  5  6
dp:   0  1  1  2  2  1  2
                          └─ answer (5+1)

---

3. The Dry Run

coins = [1, 2, 5], amount = 11

a	Tries (coin: from)	dp[a]
0	base	0
1	1:dp[0]+1=1	1
2	1:dp[1]+1=2 ; 2:dp[0]+1=1	1
3	1:dp[2]+1=2 ; 2:dp[1]+1=2	2
4	1:dp[3]+1=3 ; 2:dp[2]+1=2	2
5	1,2 give 3 ; 5:dp[0]+1=1	1
6	min over coins	2
7	…	2
8	…	3
9	…	3
10	5:dp[5]+1=2	2
11	5:dp[6]+1=3	3

Return 3.

---

4. Java Solution

Brute Force (Memoized Recursion)

class Solution {
    public int coinChange(int[] coins, int amount) {
        Integer[] memo = new Integer[amount + 1];
        int res = dfs(coins, amount, memo);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    private int dfs(int[] coins, int a, Integer[] memo) {
        if (a < 0) return Integer.MAX_VALUE;
        if (a == 0) return 0;
        if (memo[a] != null) return memo[a];
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            int sub = dfs(coins, a - c, memo);
            if (sub != Integer.MAX_VALUE) best = Math.min(best, sub + 1);
        }
        return memo[a] = best;
    }
}

Optimal — Bottom-up DP

class Solution {
    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 (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Time: (O(\text{amount} \cdot \text{coins.length})) Space: (O(\text{amount}))

---

5. The “Java vs. Others” Edge

• Arrays.fill(dp, amount + 1) is a clean sentinel — avoids Integer.MAX_VALUE overflow on +1.
• For the count-of-ways twin (LC 518), swap loop order: outer = coin, inner = amount.
• BFS by amount level is an alternative that gives the shortest path of coins — same complexity but extra queue overhead.

---

6. Complexity Summary

Approach	Time	Space	Notes
Memoized DFS	O(amount × C)	O(amount)	Same as DP but recursive
Bottom-up DP	O(amount × C)	O(amount)	Cleanest