💰 Coin Change: The First-Principles Journey

From intuitive greedy attempts to discovering optimal substructure - how a problem-solver uncovers the dynamic programming solution

THE PROBLEM (LC 322)

Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

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

You may assume that you have an infinite number of each kind of coin.

Example 1:

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

Example 2:

Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot make 3 with only 2-value coins

Example 3:

Input: coins = [1], amount = 0
Output: 0
Explanation: No coins needed for amount 0

Constraints:

• 1 ≤ coins.length ≤ 12
• 1 ≤ coins[i] ≤ 2³¹ - 1
• 0 ≤ amount ≤ 10⁴

---

🧠 DESIGNER'S BRAIN: The Discovery Process

Step 1: What are we REALLY being asked?

Before touching code, let's understand the problem deeply:

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

Question: What's the MINIMUM number of coins to make 11?

The messy initial thoughts:

FIRST INSTINCT: GREEDY?

"I could use greedy: take largest coin first?"

Let's try:

• Use 5 → remaining = 6
• Use 5 → remaining = 1
• Use 1 → remaining = 0
• Result: 5, 5, 1 → 3 coins ✓

Looks good! But wait... let's test with another example:

coins = [1, 3, 4], amount = 6

Greedy approach:

• Use 4 → remaining = 2
• Use 1 → remaining = 1
• Use 1 → remaining = 0
• Result: 4, 1, 1 → 3 coins

Optimal approach:

• Use 3 → remaining = 3
• Use 3 → remaining = 0
• Result: 3, 3 → 2 coins ✓

Greedy fails! This isn't a greedy problem.

"Maybe try all combinations?"

Yes! But how do we organize this search efficiently?

---

Step 2: The KEY INSIGHT (Optimal Substructure)

What property makes this solvable with dynamic programming?

OPTIMAL SUBSTRUCTURE DISCOVERY

If I know the minimum coins for amounts n-1, n-2, n-5, I can find minimum for n.

Let's discover this through example:

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

To make 11, I MUST use one of 5 as a coin.

The key realization:

• If I use coin 1 → I need min coins for (11-1=10) + 1
• If I use coin 2 → I need min coins for (11-2=9) + 1
• If I use coin 5 → I need min coins for (11-5=6) + 1

Answer = minimum of these three choices!

The "aha moment": The problem breaks into smaller identical problems!

---

Step 3: What's the natural way to explore this?

Recursive thinking (how humans naturally think):

"To solve 11, I need to solve 10, 9, and 6 first"

"To solve 10, I need to solve 9, 8, and 5 first"

And so on...

Base case: amount = 0 needs 0 coins

THE THOUGHT PROCESS CHRONOLOGICALLY

1. First: Recognize we need to try all coins
2. Second: Realize each choice leads to a smaller problem
3. Third: Identify we're solving same subproblems repeatedly
4. Fourth: Realize we can cache results (memoization)
5. Fifth: Notice we can build bottom-up instead

---

💻 CODER'S BRAIN: Implementation Journey

Version 1: Pure Recursion (The Natural Discovery)

WHY START HERE?

Because this mirrors how you'd solve it by hand. No optimization, just raw logic.

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Edge case: if amount is 0, we need 0 coins
        if (amount == 0) return 0;

        int result = coinChangeRecursive(coins, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int coinChangeRecursive(int[] coins, int amount) {
        // Base case: no amount left = 0 coins needed
        if (amount == 0) return 0;

        // Invalid case: negative amount = impossible
        if (amount < 0) return Integer.MAX_VALUE;

        int minCoins = Integer.MAX_VALUE;

        // Try using each coin as the "next" coin
        for (int coin : coins) {
            int subResult = coinChangeRecursive(coins, amount - coin);

            // If subproblem was solvable, consider it
            if (subResult != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, subResult + 1);
            }
        }

        return minCoins;
    }
}

🔍 Let's Trace an Example

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

coinChange(11)
├─ try coin 1 → coinChange(10)
│  ├─ try coin 1 → coinChange(9)
│  │  ├─ try coin 1 → coinChange(8)
│  │  │  └─ ... keeps going
│  │  ├─ try coin 2 → coinChange(7)
│  │  └─ try coin 5 → coinChange(4)
│  ├─ try coin 2 → coinChange(8)
│  └─ try coin 5 → coinChange(5)
├─ try coin 2 → coinChange(9)
└─ try coin 5 → coinChange(6)
    ├─ try coin 1 → coinChange(5)  ← LOOK! We solve this AGAIN
    ├─ try coin 2 → coinChange(4)
    └─ try coin 5 → coinChange(1)

THE PROBLEM

We're recalculating coinChange(5), coinChange(4), etc. MANY times!

Time Complexity: O(coins^amount) - exponential! 💥

---

Version 2: Top-Down with Memoization (The First Optimization)

THE DESIGNER'S REALIZATION

"Wait... I'm solving coinChange(5) multiple times. What if I remember the answer?"

Why this data structure?

• Array memo[]: Index represents amount, value represents min coins
• Why array? Fast O(1) lookup by amount
• Size: amount + 1 to include 0

class Solution {
    public int coinChange(int[] coins, int amount) {
        // memo[i] = minimum coins needed for amount i
        // -1 means "not computed yet"
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -1);

        int result = coinChangeTopDown(coins, amount, memo);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int coinChangeTopDown(int[] coins, int amount, int[] memo) {
        // Base cases
        if (amount == 0) return 0;
        if (amount < 0) return Integer.MAX_VALUE;

        // Check if already computed
        if (memo[amount] != -1) {
            return memo[amount];
        }

        int minCoins = Integer.MAX_VALUE;

        // Try each coin
        for (int coin : coins) {
            int subResult = coinChangeTopDown(coins, amount - coin, memo);

            if (subResult != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, subResult + 1);
            }
        }

        // Store and return
        memo[amount] = minCoins;
        return minCoins;
    }
}

🔍 What Changed?

PERFORMANCE TRANSFORMATION

Before memoization:

• coinChange(5) called 10 times → each time recalculates

After memoization:

• coinChange(5) called 10 times → computed once, cached 9 times

Time Complexity: O(amount × coins)

• Each of amount states computed once
• Each computation tries all coins

Space Complexity: O(amount) for memo + O(amount) recursion stack

---

Version 3: Bottom-Up DP (The Ultimate Insight)

THE DESIGNER'S BREAKTHROUGH

"I'm building from smaller amounts to larger. Why not just... start from smallest?"

Chronological discovery:

1. "To find answer for 11, I need answers for smaller amounts"
2. "What if I compute 1, then 2, then 3... up to 11?"
3. "Then when I reach 11, all smaller answers are ready!"
4. "No recursion needed!"

Why this approach?

Prerequisite insight: If we solve problems in increasing order of amount, each problem's dependencies are already solved.

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] = minimum coins to make amount i
        int[] dp = new int[amount + 1];

        // Initialize: all amounts are impossible by default
        Arrays.fill(dp, amount + 1); // Using amount+1 as "infinity"

        // Base case: 0 amount needs 0 coins
        dp[0] = 0;

        // Build up from amount 1 to target amount
        for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {

            // Try using each coin for current amount
            for (int coin : coins) {

                // Can we use this coin?
                if (currentAmount >= coin) {
                    // dp[currentAmount] = min of:
                    //   - current best
                    //   - using this coin + best for remaining amount
                    dp[currentAmount] = Math.min(
                        dp[currentAmount],
                        dp[currentAmount - coin] + 1
                    );
                }
            }
        }

        // If still "infinity", it's impossible
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

🔍 Detailed Walkthrough

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

STEP-BY-STEP EXECUTION

Initial state:

dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
      ↑
   amount=0

Building amount = 1:

• try coin 1: dp[1] = min(∞, dp[0]+1) = 1
• try coin 2: can't use (1 < 2)
• try coin 5: can't use (1 < 5)

dp = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

Building amount = 2:

• try coin 1: dp[2] = min(∞, dp[1]+1) = 2
• try coin 2: dp[2] = min(2, dp[0]+1) = 1 ← Better!
• try coin 5: can't use

dp = [0, 1, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

Building amount = 3:

• try coin 1: dp[3] = min(∞, dp[2]+1) = 2
• try coin 2: dp[3] = min(2, dp[1]+1) = 2
• try coin 5: can't use

dp = [0, 1, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]

Building amount = 5:

• try coin 1: dp[5] = min(∞, dp[4]+1) = 4
• try coin 2: dp[5] = min(4, dp[3]+1) = 3
• try coin 5: dp[5] = min(3, dp[0]+1) = 1 ← Best!

dp = [0, 1, 1, 2, 2, 1, ∞, ∞, ∞, ∞, ∞, ∞]

... continuing ...

Final state:

dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
                                       ↑
                                 answer = 3

Complexity Analysis:

• Time Complexity: O(amount × coins)
• Space Complexity: O(amount) - no recursion stack!

---

🎯 EDGE CASES: Validate Your Understanding

Edge Case 1: Impossible Amount

coins = [2], amount = 3

WHY IMPOSSIBLE?

All coins are even, can't make odd amount.

How does our code handle it?

dp = [0, ∞, 1, ∞]
         ↑       ↑
      can't   still ∞
       make 1  → return -1

---

Edge Case 2: Amount = 0

coins = [1], amount = 0

Answer: 0 coins (base case)

---

Edge Case 3: Only One Coin Type

coins = [5], amount = 11

Not possible since 11 is not divisible by 5.

dp = [0, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2, ∞]
                                       ↑
                                  still ∞

---

Edge Case 4: Coin Larger Than Amount

coins = [10], amount = 5

HOW IT WORKS

Our loop skips it because currentAmount >= coin is false.

The condition naturally handles this edge case!

---

🧩 META-PROCESS: How to Approach ANY DP Problem

THE FRAMEWORK

1. Identify if it's DP:

• Are you finding optimal value? (min/max/count)
• Can you break into smaller identical subproblems?
• Do subproblems overlap?

2. Define the state:

• "What information do I need to solve this?"
• Here: Just the amount remaining

3. Find the recurrence:

• "How does this state relate to smaller states?"
• Here: dp[i] = min(dp[i - coin] + 1) for all coins

4. Identify base case:

• "What's the simplest case I know the answer to?"
• Here: dp[0] = 0

5. Decide direction:

• Top-down (recursion + memo): Natural thinking
• Bottom-up (iteration): Optimal implementation

---

🔗 CONNECTING TO PRIOR KNOWLEDGE

PATTERN CONNECTIONS

This is like:

• Fibonacci: Building answers from smaller problems
• Climbing Stairs: Choose from multiple options at each step
• Graph traversal: Exploring all paths, finding shortest

Distinctive differences:

• Unlike Fibonacci (2 previous), here we look back by coin amounts
• Unlike graph BFS (finds shortest path), here we use DP (finds min cost)
• Unbounded: Can use same coin multiple times (vs 0/1 knapsack)

---

🎓 Complete Implementations

JavaScript Implementation

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    // dp[i] = minimum coins to make amount i
    const dp = new Array(amount + 1).fill(amount + 1);

    // Base case: 0 amount needs 0 coins
    dp[0] = 0;

    // Build up from amount 1 to target
    for (let currentAmount = 1; currentAmount <= amount; currentAmount++) {
        // Try each coin
        for (const coin of coins) {
            if (currentAmount >= coin) {
                dp[currentAmount] = Math.min(
                    dp[currentAmount],
                    dp[currentAmount - coin] + 1
                );
            }
        }
    }

    // If still "infinity", impossible
    return dp[amount] > amount ? -1 : dp[amount];
};

---

Java Implementation

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] = minimum coins to make amount i
        int[] dp = new int[amount + 1];

        // Initialize with "infinity" (amount + 1 works)
        Arrays.fill(dp, amount + 1);

        // Base case: 0 amount needs 0 coins
        dp[0] = 0;

        // Build up from amount 1 to target
        for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
            // Try each coin
            for (int coin : coins) {
                if (currentAmount >= coin) {
                    dp[currentAmount] = Math.min(
                        dp[currentAmount],
                        dp[currentAmount - coin] + 1
                    );
                }
            }
        }

        // If still "infinity", impossible
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

💡 Deep Understanding Questions

TEST YOUR UNDERSTANDING

Question 1: Why can't we sort coins and use greedy?

Click to reveal answer

Greedy algorithms make locally optimal choices, but coin change requires globally optimal solutions.

Example: coins = [1, 3, 4], amount = 6

• Greedy: 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

The largest coin isn't always part of the optimal solution!

---

Question 2: What if coins = [1]? Does our solution simplify?

Click to reveal answer

Yes! If we only have coin value 1:

• dp[i] = dp[i-1] + 1 = i
• We need exactly amount coins
• The DP simplifies to a direct calculation

But our general solution still works correctly!

---

Question 3: How would you modify this to return the actual coins used?

Click to reveal answer

Track the path:

int[] dp = new int[amount + 1];
int[] parent = new int[amount + 1];  // Track which coin was used

// During DP:
if (dp[currentAmount - coin] + 1 < dp[currentAmount]) {
    dp[currentAmount] = dp[currentAmount - coin] + 1;
    parent[currentAmount] = coin;  // Remember the coin
}

// Backtrack to find coins:
List<Integer> coins = new ArrayList<>();
int curr = amount;
while (curr > 0) {
    coins.add(parent[curr]);
    curr -= parent[curr];
}

---

Question 4: What if we wanted the MAXIMUM number of coins?

Click to reveal answer

Change Math.min to Math.max!

This would find the way to make the amount using the most coins possible.

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

• Min: 3 coins (5 + 5 + 1)
• Max: 11 coins (1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)

---

🎯 Key Takeaways

THE JOURNEY SUMMARY

1. Pattern Recognition:

• Greedy doesn't work → need to explore all possibilities
• Overlapping subproblems → perfect for DP

2. State Definition:

• dp[i] = minimum coins needed for amount i
• Simple 1D array suffices

3. Recurrence Relation:

• For each coin, try using it and take the minimum
• dp[i] = min(dp[i], dp[i - coin] + 1)

4. Base Case:

• dp[0] = 0 (no coins needed for zero amount)

5. Direction:

• Build from bottom-up (1 to amount)
• Each state depends only on smaller amounts

---

🔄 Related Problems

PATTERN FAMILY: UNBOUNDED KNAPSACK

Same pattern, different questions:

1. Coin Change ← You are here

   • Question: Minimum coins to make amount?

2. Coin Change II (LC 518)

   • Question: How many ways to make amount?
   • Change: Count combinations instead of minimum

3. Minimum Cost For Tickets (LC 983)

   • Question: Minimum cost for travel days?
   • Similar: Choose from multiple options repeatedly

4. Perfect Squares (LC 279)

   • Question: Minimum perfect squares to sum to n?
   • Same: Unbounded choice, minimize count

---

🎓 Where Might Confusion Still Lurk?

Reflect on these questions:

1. Why does dp[i - coin] + 1 represent using a coin?
2. Why do we initialize with amount + 1 instead of Integer.MAX_VALUE?
3. How does the condition currentAmount >= coin prevent errors?
4. Why can we use the same coin multiple times?

Understanding your confusion points is how you deepen your mastery.

The questions you ask reveal the insights you're about to discover.

---

🌟 The Meta-Lesson

THE TRANSFORMATION

From confusion to clarity:

1. ❌ "Try greedy" → Fails on some inputs
2. 🤔 "Try all possibilities" → Too slow
3. 💡 "Cache repeated work" → Memoization works
4. ✨ "Build bottom-up" → Optimal solution

The pattern emerges:

• Recognize optimal substructure
• Identify overlapping subproblems
• Define state and recurrence
• Choose implementation strategy

Master this process, not just this problem.

The thinking framework transfers to hundreds of DP problems.

---

FINAL WISDOM

The problem transformation is the breakthrough.

Once you see "minimum coins" as "minimize over all coin choices at each step," the solution becomes a natural application of dynamic programming.

Master the transformation, and the implementation follows naturally.