Coin Change (LC 322)

Pattern: Dynamic Programming — Unbounded Knapsack (coin reuse)
Difficulty: Medium
Key Concept: dp[amount] = minimum coins to make that amount; try every coin as the “last” coin added.

Problem Statement

You are given an integer array coins representing coin denominations (all positive) and an integer amount representing a target total.

Return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination, return -1.

You may use each denomination as many times as you want (unbounded supply).

Input: coins — distinct positive integers; amount — non-negative integer.

Output: Minimum coin count, or -1 if impossible.

Example: coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1).

---

1. Algorithm & Pseudocode

Brute force: Try all combinations of coins (reuse allowed) until sum equals amount; track minimum count. Exponential in the branching factor.

Optimal (bottom-up DP)

dp[0] = 0
for i from 1 to amount:
    dp[i] = INF_SENTINEL  // "impossible" so far
    for each coin c in coins:
        if i >= c and dp[i - c] is reachable:
            dp[i] = min(dp[i], dp[i - c] + 1)
return dp[amount] if reachable else -1

dp[i] = minimum coins to form sum i. Transition: last coin is c, so previous sum was i - c using dp[i-c] coins.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why dp[0] = 0?
   Zero coins are needed to make sum 0. This seeds transitions: dp[c] = min(dp[c], dp[0] + 1) = 1 when a single coin c equals the amount.

2. Why initialize other entries to amount + 1?
   You need a value larger than any feasible answer. The worst case is amount coins of value 1, so any answer is at most amount. Using amount + 1 as “infinity” keeps min updates correct. Be careful with Integer.MAX_VALUE because dp[i-c] + 1 can overflow.

3. Why is this “unbounded knapsack”?
   You can pick the same coin type repeatedly—like unlimited items of the same weight/value in knapsack variants. The inner loop over coins for each i naturally allows reuse.

4. Why not greedy?
   Greedy (always take largest coin) fails for some denominations (e.g., [1, 3, 4], amount = 6: greedy picks 4+1+1 = 3 coins, optimal is 3+3 = 2).

5. Order of loops: Outer loop is amount increasing; inner is coins. That ensures when you use dp[i-c], smaller sums are already finalized.

---

3. The Dry Run

Sample: coins = [1, 2, 5], amount = 11.

Initialize: dp[0] = 0, dp[1..11] = 12 (i.e., amount + 1 sentinel).

Abbreviation: after processing sum i, we show dp[i] when it changes from a previous row logic. Full trace for sums 0–11:

i	After trying coins, dp[i]	How it was achieved (one optimal last coin)
0	0	base
1	1	dp[0]+1 with coin 1
2	1	dp[1]+1 with 1 or dp[0]+1 with 2 → min is 1 (use one 2)
3	2	e.g. 2+1
4	2	two 2s
5	1	one 5
6	2	5+1
7	2	5+2
8	3	5+2+1
9	3	5+2+2
10	2	5+5
11	3	5+5+1

Answer: dp[11] = 3.

---

4. Java Solution

Brute Force

DFS trying every coin at each step. Time: roughly O(S^n) branching in worst case (S = number of coin types, depth up to amount in pathological cases). Space: O(amount) recursion depth.

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int ans = dfs(coins, amount);
        return ans >= Integer.MAX_VALUE - 1 ? -1 : ans;
    }

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

Optimal

Bottom-up DP with amount + 1 sentinel. Time: O(amount × coins.length). Space: O(amount).

import java.util.Arrays;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (c <= i) {
                    dp[i] = Math.min(dp[i], dp[i - c] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

5. The “Java vs. Others” Edge

• Arrays.fill(dp, amount + 1): Common Java idiom for “infinity” in coin/DP problems. In C++ you might use vector<int>(amount+1, INT_MAX) and careful +1 in transitions to avoid overflow.
• Avoid Integer.MAX_VALUE as sentinel when you compute min + 1; use amount + 1 instead (problem-specific safe upper bound).
• Unbounded knapsack mental model: Same pattern as “minimum items to hit weight” with unlimited copies—Java solution is identical in structure to C++; Python often uses float('inf') for init.
• Top-down memo is also popular in interviews; bottom-up is often easier to reason about for “minimum coins.”

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	Exponential (e.g. O(S^amount) style worst case)	O(amount) stack	TLE on LeetCode for typical constraints
Optimal	O(amount × |coins|)	O(amount)	Classic unbounded knapsack DP; sentinel amount + 1