💰 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 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⁴

Section 1: Discovery & Problem Understanding

1.1 Problem Analysis & Initial Thinking

🧠 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?

1.2 Thought Process & Strategy

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

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

1.3 Prerequisites & Core Insights

The Prerequisite Insight: Unlimited Coins

THE UNBOUNDED INSIGHT

Key difference from 0/1 Knapsack:

0/1 Knapsack: Each item can be used at most once
Coin Change: Each coin can be used unlimited times

This is called the "Unbounded Knapsack" pattern.

Why it matters:

After using coin of value c, we can use the same coin again
dp[amount] depends on dp[amount - coin], which might have already used the same coin
No need to track which coins we've used

The Recurrence Relation

What defines each subproblem?

Only one parameter: the remaining amount to make.

STATE DEFINITION

dp[amount] = minimum number of coins needed to make this amount

For any amount, we try every coin and take the minimum of dp[amount - coin] + 1 for all coins.

Base case: dp[0] = 0 (zero amount needs zero coins)

Boundary condition: If amount < coin, skip that coin (it's too large)

Section 2: Implementation & Deep Understanding

2.1 Solution Implementation

This section presents three progressively optimized solutions that represent the natural evolution of thought from brute force to dynamic programming.

Approach 1: Recursive Unoptimized (Brute Force)

This is the first thing that comes to mind - try all possible combinations.

public class CoinChangeRecursive {
    public int coinChange(int[] coins, int amount) {
        int result = coinChangeRecursive(coins, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int coinChangeRecursive(int[] coins, int amount) {
        // Base case: exact change reached
        if (amount == 0) {
            return 0;
        }

        // Invalid case: went negative
        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;
    }
}

WHY THIS IS TOO SLOW

Problem: We solve the same subproblems repeatedly!

Example trace for 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)

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

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

For amount = 11 with 3 coins, this explores potentially 3^11 = 177,147 paths!

Approach 2: Recursive Optimized (Top-Down with Memoization)

The critical optimization: Remember solutions to avoid recomputing them.

public class CoinChangeMemoized {
    private Integer[] memo;

    public int coinChange(int[] coins, int amount) {
        // memo[i] = minimum coins needed for amount i
        // Use Integer (object) to distinguish uncomputed (null) from computed values
        memo = new Integer[amount + 1];

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

    private int coinChangeTopDown(int[] coins, int amount) {
        // Base case: exact change reached
        if (amount == 0) {
            return 0;
        }

        // Invalid case: went negative
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }

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

        int minCoins = Integer.MAX_VALUE;

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

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

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

THE MEMOIZATION BREAKTHROUGH

What changed?

Added a memoization array memo[amount + 1]
Before computing, check if we've seen this amount
After computing, store the result

Impact:

Time complexity: O(coins^amount) → O(amount × coins)
Each unique amount is computed exactly once
Subsequent calls return cached results in O(1)

Why this works:

Parameter remaining ranges from 0 to amount (amount+1 values)
Each computation tries all coins (coins iterations)
Total work: amount × coins instead of exponential

Example: For amount = 11:

minCoins(5) called 10 times in brute force
minCoins(5) computed once, cached 9 times in memoization

Approach 3: Bottom-Up Dynamic Programming (Iterative)

The final evolution: Eliminate recursion entirely by computing iteratively.

public class CoinChangeBottomUp {
    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 as infinity)
        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];
    }
}

FROM TOP-DOWN TO BOTTOM-UP

What changed?

Replaced recursion with iteration
Build from smallest amount (0) to target amount
No call stack overhead
More predictable memory access patterns (cache-friendly)

Same time complexity O(amount × coins), but:

No recursion overhead (no call stack)
Better cache performance (sequential access)
Easier to understand execution order
Simpler space complexity (just O(amount))

Why we initialize with amount + 1:

Represents "impossible" (infinity)
Any valid solution needs ≤ amount coins (using all 1s)
So amount + 1 is always larger than any valid solution
Better than Infinity because it works with integer comparisons

Complexity Comparison

Approach	Time	Space	When to Use
Recursive Brute Force	O(coins^amount)	O(amount)	❌ Never in production - educational only
Top-Down Memoization	O(amount × coins)	O(amount) + O(amount)	✓ When recursion is more intuitive
Bottom-Up Tabulation	O(amount × coins)	O(amount)	✓ Production code - most efficient

2.2 Key Concepts & Mechanics

Understanding the Key Line

VISUALIZING THE RECURRENCE

Can you visualize what dp[currentAmount - coin] + 1 represents?

currentAmount - coin is the remaining amount after using this coin
dp[currentAmount - coin] is the minimum coins needed for that remaining amount
+ 1 accounts for the coin we just used

Example: Making amount 11 with coin 5:

dp[11] = dp[6] + 1
"Minimum coins for 11" = "Minimum coins for 6" + "the coin 5 we just used"

This is the coder's translation of the designer's insight about "reduced subproblems"!

Why Initialize with `amount + 1`?

THE INFINITY TRICK

Question: Why not use Infinity or Integer.MAX_VALUE?

Answer: Mathematical elegance and safety!

Reasoning:

Any valid solution uses ≤ amount coins (imagine all 1-value coins)
So amount + 1 is always larger than any valid solution
It represents "impossible" without integer overflow risks

Example: For amount = 5, coins = [2] (can't make 5 with only 2s):

dp = [0, 6, 1, 6, 2, 6] where 6 represents "impossible"
Since dp[5] = 6 > amount (5), return -1

Why not Infinity?

Infinity + 1 = Infinity (correct mathematically)
But Integer.MAX_VALUE + 1 causes overflow in Java!
amount + 1 is safe and works perfectly

The Unbounded Nature

WHY SAME COIN CAN BE REUSED

Question: How can we use the same coin multiple times?

Answer: The state doesn't track which coins we've used!

Key insight:

0/1 Knapsack: dp[i][amount] includes index i (which items considered)
Coin Change: dp[amount] only tracks amount (no index needed)

Why this works:

When computing dp[11], we can look at dp[6]
dp[6] might have already used a coin of value 5
When we do dp[11] = dp[6] + 1 (using coin 5 again), we're reusing coin 5!

Example trace:

dp[5] = 1  (one coin of value 5)
dp[10] = dp[5] + 1 = 2  (two coins of value 5)
dp[15] = dp[10] + 1 = 3  (three coins of value 5)

Each step reuses the same coin type!

2.3 Edge Cases & Validation

🎯 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?

Brute force:

Tries all combinations, all return Infinity
Returns -1 ✓

Memoized:

Computes memo[3] = Infinity
Returns -1 ✓

Bottom-up:

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

✓ All approaches handle it correctly!

Edge Case 2: Amount = 0

coins = [1], amount = 0

Expected: 0 coins

All three approaches:

Brute force: base case returns 0 ✓
Memoized: base case returns 0 ✓
Bottom-up: dp[0] = 0 ✓

Edge Case 3: Only One Coin Type

coins = [5], amount = 11

Not possible since 11 is not divisible by 5.

Bottom-up trace:

dp = [0, 12, 12, 12, 12, 1, 12, 12, 12, 12, 2, 12]
                                             ↑
                                        still 12 > 11
                                        → return -1

Edge Case 4: Coin Larger Than Amount

coins = [10], amount = 5

HOW IT WORKS

Bottom-up approach:

Condition currentAmount >= coin is false for all iterations
Never enters the min calculation
dp[5] remains at initial value amount + 1 = 6
Returns -1 ✓

The condition naturally handles this edge case!

Edge Case 5: Multiple Valid Solutions

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

Multiple valid solutions exist:

5 + 5 + 1 = 3 coins (optimal)
5 + 2 + 2 + 2 = 4 coins
5 + 2 + 2 + 1 + 1 = 5 coins
1 + 1 + ... (11 times) = 11 coins

Our algorithm finds the optimal: 3 coins ✓

Edge Case 6: Amount Equals a Single Coin

coins = [1, 5, 10], amount = 10

Expected: 1 coin (use the 10-value coin)

Bottom-up trace:

dp[10] = min(
  dp[10],           // current = 11
  dp[10-1] + 1,     // 10 = dp[9] + 1 (using coin 1)
  dp[10-5] + 1,     // 3 = dp[5] + 1 (using coin 5)
  dp[10-10] + 1     // 1 = dp[0] + 1 = 1 (using coin 10) ← Best!
)

✓ Correctly finds minimum of 1 coin

Section 3: Mastery & Visualization

3.1 Practical Examples/Visualization

Worked Example: Trace Through All Three Approaches

Let's trace a small example to see how each approach works:

Input:

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

Approach 1: Recursive Brute Force - Decision Tree (Partial)

minCoins(11)
├─ use coin 1 → minCoins(10) + 1
│  ├─ use coin 1 → minCoins(9) + 1
│  │  ├─ use coin 1 → minCoins(8) + 1
│  │  │  └─ ... (eventually reaches 0)
│  │  ├─ use coin 2 → minCoins(7) + 1
│  │  └─ use coin 5 → minCoins(4) + 1
│  │     ├─ use coin 1 → minCoins(3) + 1
│  │     ├─ use coin 2 → minCoins(2) + 1
│  │     │  ├─ use coin 1 → minCoins(1) + 1 → 0 + 1 = 1 → 2
│  │     │  └─ use coin 2 → minCoins(0) + 1 → 0 + 1 = 1 → best!
│  │     │  → min(2, 1) = 1
│  │     └─ ...
│  │     → returns 2
│  │  → returns 3
│  ├─ use coin 2 → minCoins(8) + 1
│  └─ use coin 5 → minCoins(5) + 1
│     ├─ use coin 1 → minCoins(4) + 1  ← DUPLICATE WORK!
│     ├─ use coin 2 → minCoins(3) + 1
│     └─ use coin 5 → minCoins(0) + 1 → 0 + 1 = 1 ← Best for 5!
│     → returns 1
│  → returns 2
├─ use coin 2 → minCoins(9) + 1
└─ use coin 5 → minCoins(6) + 1
   ├─ use coin 1 → minCoins(5) + 1  ← DUPLICATE WORK AGAIN!
   ├─ use coin 2 → minCoins(4) + 1
   └─ use coin 5 → minCoins(1) + 1
   → returns 2
→ min(10, 9, 2+1) = 3 ✓

Notice: minCoins(5), minCoins(4), etc. computed multiple times!

Approach 2: Top-Down Memoization - Computation Order

Same recursive structure, but with caching:

Call minCoins(11)
  → Not in memo, compute
  → Try coin 1: Call minCoins(10)
    → Not in memo, compute
    → Try coin 1: Call minCoins(9)
      → Not in memo, compute
      → ... eventually computes down to 0
      → memo[9] = 4
    → Try coin 2: Call minCoins(8)
      → Not in memo, compute
      → memo[8] = 3
    → Try coin 5: Call minCoins(5)
      → Not in memo, compute
      → Try coin 5: Call minCoins(0) = 0 (base case)
      → memo[5] = 1
    → memo[10] = min(memo[9]+1, memo[8]+1, memo[5]+1) = min(5, 4, 2) = 2
  → Try coin 2: Call minCoins(9)
    → IN MEMO! Return 4 immediately (no recomputation!)
  → Try coin 5: Call minCoins(6)
    → Not in memo, compute
    → Try coin 5: Call minCoins(1)
      → Not in memo, compute
      → memo[1] = 1
    → memo[6] = 2
  → memo[11] = min(memo[10]+1, memo[9]+1, memo[6]+1) = min(3, 5, 3) = 3 ✓

Each amount computed exactly once and cached!

Approach 3: Bottom-Up - DP Table

Build the table systematically:

Initial state:

dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
     ↑ base case, rest initialized to "infinity" (amount+1 = 12)

After processing amount = 1:

Try coin 1: dp[1] = min(12, dp[1-1]+1) = min(12, 0+1) = 1
Try coin 2: skip (1 < 2)
Try coin 5: skip (1 < 5)

dp = [0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

After processing amount = 2:

Try coin 1: dp[2] = min(12, dp[2-1]+1) = min(12, 1+1) = 2
Try coin 2: dp[2] = min(2, dp[2-2]+1) = min(2, 0+1) = 1 ← Better!
Try coin 5: skip (2 < 5)

dp = [0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]

After processing amount = 5:

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

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

Continuing through amount = 11:

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

Detailed calculation for amount = 11:

dp[11] = min(
  12,                    // initial value
  dp[11-1] + 1 = 2+1=3,  // use coin 1
  dp[11-2] + 1 = 3+1=4,  // use coin 2
  dp[11-5] + 1 = 2+1=3   // use coin 5
) = 3

💡 Deep Understanding Questions

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

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?

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: return amount

But our general solution still works correctly!

Question 3: Why does dp[i - coin] + 1 represent using a coin?

Breaking it down:

dp[i - coin] = minimum coins needed for the remaining amount
+ 1 = the coin we just used
Together: "Use this coin, then optimally solve the rest"

Example: For amount 11, using coin 5:

dp[11] = dp[6] + 1
"To make 11, use one coin of value 5, then make the remaining 6 optimally"

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

Track the path: Use an additional parent array to track which coin was used for each amount. Then backtrack from the target amount to reconstruct the actual coins used.

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

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)

Question 6: Why can we use the same coin multiple times?

Because the state doesn't track which coins we've used!

0/1 Knapsack: State includes "which items we've considered" → can't reuse
Coin Change: State only includes "remaining amount" → can reuse

When computing dp[10] using coin 5, we look at dp[5] which might have already used coin 5. That's perfectly fine - we're reusing the coin!

3.2 Framework & Pattern Recognition

🧩 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, easier to start
Bottom-up (iteration): Optimal implementation, better performance

6. Start with brute force:

Get the logic right first
Don't worry about efficiency

7. Add memoization:

Identify overlapping subproblems
Cache results

8. Convert to bottom-up:

Eliminate recursion
Build iteratively

9. Optimize space:

Can you reduce dimensions?
Here: Already optimal at O(amount)

🔗 CONNECTING TO PRIOR KNOWLEDGE

PATTERN CONNECTIONS

This is like:

Fibonacci: Building answers from smaller problems
Climbing Stairs: Choose from multiple options at each step
0/1 Knapsack: Optimize with constraints

Distinctive differences:

Unlike Fibonacci: We look back by coin amounts (variable), not fixed 2 previous
Unlike Climbing Stairs: We minimize count, not count ways
Unlike 0/1 Knapsack: Items (coins) can be reused unlimited times (unbounded)

PATTERN FAMILY: UNBOUNDED KNAPSACK

Same pattern, different questions:

Coin Change ← You are here
- Question: Minimum coins to make amount?
- Focus: Minimize count
Coin Change II (LC 518)
- Question: How many ways to make amount?
- Focus: Count combinations
Perfect Squares (LC 279)
- Question: Minimum perfect squares to sum to n?
- Same: Unbounded choice, minimize count
- Coins are: 1, 4, 9, 16, 25, ...
Minimum Cost For Tickets (LC 983)
- Question: Minimum cost for travel days?
- Similar: Choose from multiple options repeatedly
Unbounded Knapsack (Classic)
- Question: Maximum value with unlimited items?
- Same pattern, maximize instead of minimize

The pattern template: For each amount from 1 to target, try using each item and optimize (min/max/count) based on the subproblem dp[amount - cost[item]].

Evolution of Solution Approaches

Brute Force Recursion (exponential)
    ↓ (add caching)
Top-Down Memoization (polynomial)
    ↓ (eliminate recursion)
Bottom-Up Tabulation (optimal)
    ↓ (already optimal space)
O(amount) space - can't reduce further!

Each step preserves correctness while improving efficiency!

3.3 Key Takeaways & Summary

🎯 Key Takeaways

THE JOURNEY SUMMARY

1. Pattern Recognition:

Greedy doesn't work → need to explore all possibilities
Overlapping subproblems → perfect for DP
Unlimited coin use → Unbounded Knapsack pattern

2. State Definition:

dp[i] = minimum coins needed for amount i
Simple 1D array suffices (no need to track coin index)

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 (0 to amount)
Each state depends only on smaller amounts

6. Progression:

Brute force → understand the logic
Memoization → eliminate redundant work
Bottom-up → optimal implementation

The Three Pillars of Coin Change Mastery

PILLAR 1: OPTIMAL SUBSTRUCTURE

Understand the recursive insight:

minCoins(amount) = min(
  minCoins(amount - coin1) + 1,
  minCoins(amount - coin2) + 1,
  minCoins(amount - coin3) + 1,
  ...
)

To make any amount, we must use one of the available coins. The minimum is found by trying all coins.

This is the foundation. Everything else is optimization.

PILLAR 2: MEMOIZATION INSIGHT

Recognize overlapping subproblems:

The same amounts are computed many times in brute force
Cache results to solve each amount once
Transform O(coins^amount) → O(amount × coins)

This is the breakthrough.

PILLAR 3: ITERATIVE OPTIMIZATION

Convert recursion to iteration:

Build table from 0 to target amount
Eliminate call stack overhead
Better cache performance
Production-ready solution

This is the production solution.

🌟 The Meta-Lesson

THE TRANSFORMATION

From confusion to clarity:

❌ "Try greedy" → Fails on some inputs
🤔 "Try all possibilities recursively" → Too slow (exponential)
💡 "Cache repeated work (memoization)" → Much faster (polynomial)
✨ "Build bottom-up iteratively" → Optimal solution

The pattern emerges:

Recognize optimal substructure (recursive structure)
Identify overlapping subproblems (same amounts computed multiple times)
Define state and recurrence (what info needed, how states relate)
Start with brute force → add memoization → convert to bottom-up

Master this process, not just this problem.

The thinking framework transfers to hundreds of DP problems.

🎓 Where Might Confusion Still Lurk?

Reflect on these questions:

Why does dp[i - coin] + 1 represent using a coin?
Why do we initialize with amount + 1 instead of Infinity?
How does the condition currentAmount >= coin prevent errors?
Why can we use the same coin multiple times?
When to use top-down vs bottom-up?
How is this different from 0/1 Knapsack?

Understanding your confusion points is how you deepen your mastery.

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

FINAL WISDOM

The problem transformation is the breakthrough.

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

Master the transformation first (brute force), add memoization (top-down), then optimize to iteration (bottom-up), and exponential becomes polynomial.

Three solutions. One pattern. Infinite applications.

Section 1: Discovery & Problem Understanding​

1.1 Problem Analysis & Initial Thinking​

🧠 DESIGNER'S BRAIN: The Discovery Process​

1.2 Thought Process & Strategy​

Step 2: The KEY INSIGHT (Optimal Substructure)​

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

1.3 Prerequisites & Core Insights​

The Prerequisite Insight: Unlimited Coins​

The Recurrence Relation​

Section 2: Implementation & Deep Understanding​

2.1 Solution Implementation​

Approach 1: Recursive Unoptimized (Brute Force)​

Approach 2: Recursive Optimized (Top-Down with Memoization)​

Approach 3: Bottom-Up Dynamic Programming (Iterative)​

Complexity Comparison​

2.2 Key Concepts & Mechanics​

Understanding the Key Line​

Why Initialize with amount + 1?​

The Unbounded Nature​

2.3 Edge Cases & Validation​

🎯 EDGE CASES: Validate Your Understanding​

Section 3: Mastery & Visualization​

3.1 Practical Examples/Visualization​

Worked Example: Trace Through All Three Approaches​

💡 Deep Understanding Questions​

3.2 Framework & Pattern Recognition​

🧩 META-PROCESS: How to Approach ANY DP Problem​

🔗 CONNECTING TO PRIOR KNOWLEDGE​

🔄 Related Problems​

Evolution of Solution Approaches​

3.3 Key Takeaways & Summary​

🎯 Key Takeaways​

The Three Pillars of Coin Change Mastery​

🌟 The Meta-Lesson​

🎓 Where Might Confusion Still Lurk?​