226. Coin Change
🔗 LeetCode Problem: 322. Coin Change
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, DP - Subsequences, Unbounded Knapsack
Problem Statement
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 coin of value 2
Example 3:
Input: coins = [1], amount = 0
Output: 0
Explanation: Need 0 coins to make amount 0
Constraints:
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
🌳 Visual Understanding - Using coins = [1, 2, 5], amount = 11
The Problem We're Solving:
Given: coins = [1, 2, 5], amount = 11
Goal: Find minimum number of coins to make amount 11
Coins available (infinite supply):
1 cent coin - unlimited
2 cent coin - unlimited
5 cent coin - unlimited
Question: What's the minimum number of coins
that add up to exactly 11 cents? 🤔
Finding All Possible Ways for 11:
Amount: 11
Option 1: Use only 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
11 = 1+1+1+1+1+1+1+1+1+1+1
Count: 11 coins
Option 2: Use 2's and 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
11 = 2+2+2+2+2+1
Count: 6 coins
Option 3: Use 5's and 1's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
11 = 5+5+1
Count: 3 coins ✓ MINIMUM!
Option 4: Use 5's and 2's
━━━━━━━━━━━━━━━━━━━━━━━━━━━
11 = 5+2+2+2
Count: 4 coins
Option 5: Mixed
━━━━━━━━━━━━━━━━━━━━━━━━━━━
11 = 5+2+2+1+1
Count: 5 coins
All counts: 11, 6, 3, 4, 5
Minimum: 3 (from 5+5+1)
Answer: 3 ✓
Why Greedy FAILS:
CRITICAL UNDERSTANDING:
Greedy approach: Always pick the LARGEST coin
Example: coins = [1, 2, 5], amount = 11
Step 1: Pick 5 (largest ≤ 11)
Used: [5]
Remaining: 11 - 5 = 6
Step 2: Pick 5 (largest ≤ 6)
Used: [5, 5]
Remaining: 6 - 5 = 1
Step 3: Pick 1 (largest ≤ 1)
Used: [5, 5, 1]
Remaining: 1 - 1 = 0
Greedy result: 5+5+1 = 3 coins ✓ (works here!)
BUT greedy FAILS on some inputs:
coins = [1, 3, 4], amount = 6
Greedy:
Pick 4: remaining = 2
Pick 1, 1: total = 4+1+1 = 3 coins ✗
Optimal:
Pick 3, 3: total = 3+3 = 2 coins ✓
Greedy doesn't always give minimum!
Must try ALL combinations! 🔑
Example Where We CAN'T Make Amount:
coins = [2], amount = 3
Try all combinations:
Use 2 once: 2 (remaining = 1, can't make it!)
Can't use 2 to make 1 (no 1 cent coin)
Impossible to make 3 with only 2 cent coins!
Answer: -1 ✓
Another example:
coins = [2, 4], amount = 3
Try all combinations:
Use 2 once: remaining = 1 (can't make 1)
Can't make odd amount with only even coins!
Answer: -1 ✓
🧠 The AHA Moment - Why This Problem Is Special
What Makes This Different?
CLASSIC UNBOUNDED KNAPSACK:
- Have items with values
- Can use each item UNLIMITED times
- Want to minimize/maximize something
COIN CHANGE (This Problem):
- Have coins with values
- Can use each coin UNLIMITED times (infinite supply)
- Want to MINIMIZE number of coins
This is the CANONICAL Unbounded Knapsack problem! 🎯
The Key Insight - Try Every Coin!
To make amount, we can use ANY coin from our list
If we use coin c:
- We've used 1 coin
- Need to make (amount - c) with remaining coins
- Remaining takes ??? coins (we need to figure this out!)
- Total: 1 + (coins needed for amount - c)
Try ALL coins:
For coin 1: 1 + (coins for amount - 1)
For coin 2: 1 + (coins for amount - 2)
For coin 5: 1 + (coins for amount - 5)
...
Pick the one that gives MINIMUM total!
This is the DP insight! 🔑
Building Intuition with Small Example:
coins = [1, 2, 5], amount = 6
Option 1: Use 1 first
6 = 1 + (remaining 5)
How many for 5? → 1 (use 5)
Total: 1 + 1 = 2
Option 2: Use 2 first
6 = 2 + (remaining 4)
How many for 4? → 2 (use 2+2)
Total: 1 + 2 = 3
Option 3: Use 5 first
6 = 5 + (remaining 1)
How many for 1? → 1 (use 1)
Total: 1 + 1 = 2
Minimum: 2 (either 1+5 or 5+1)
To find "how many for remaining", we solve same problem recursively!
This is the recursive structure! 🎯
🔴 Approach 1: Brute Force (Try All Combinations)
📐 Function Definition
Function Signature:
int coinChange(int[] coins, int amount)
What it represents:
Input Parameter coins:
- Array of available coin denominations
- Each coin can be used unlimited times
- Example: coins = [1, 2, 5]
Input Parameter amount:
- Target amount to make
- Example: amount = 11
Return Value (int): - Minimum number of coins needed to make amount - Return -1 if impossible - Example: 3 (because 11 = 5+5+1)
Purpose: - Try all possible combinations of coins - For each coin, try using it and solve remaining - Return the minimum count found - If no combination works, return -1
Key Understanding:
For coins = [1, 2, 5], amount = 11:
Use 1: 1 + solve(11-1=10)
Use 2: 1 + solve(11-2=9)
Use 5: 1 + solve(11-5=6)
For each choice, recursively solve the remaining!
Pick the choice that gives minimum total!
💡 Intuition
The simplest idea: Try using each coin, recursively solve remaining!
Think of it like a cashier making change:
Customer needs: 11 dollars
Available bills: 1, 2, 5
Cashier thinking:
"Let me try giving 5 dollar bill first"
→ Remaining: 6
→ "Now I recursively figure out best way to make 6"
"Or try giving 2 dollar bill first"
→ Remaining: 9
→ "Now I recursively figure out best way to make 9"
"Or try giving 1 dollar bill first"
→ Remaining: 10
→ "Now I recursively figure out best way to make 10"
Try all options, pick the one using fewest bills!
Same idea for coins! 🎯
📝 Implementation
class Solution {
public int coinChange(int[] coins, int amount) {
int result = helper(coins, amount);
// If impossible, return -1
return result == Integer.MAX_VALUE ? -1 : result;
}
private int helper(int[] coins, int amount) {
// Base case: amount is 0, need 0 coins
if (amount == 0) return 0;
// Base case: amount is negative, impossible
if (amount < 0) return Integer.MAX_VALUE;
int minCoins = Integer.MAX_VALUE;
// Try each coin
for (int coin : coins) {
// Use this coin, recursively solve remaining
int result = helper(coins, amount - coin);
// If this path is valid
if (result != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, 1 + result);
}
}
return minCoins;
}
}
🔍 Detailed Dry Run: coins = [1, 2, 5], amount = 6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(coins, 6)
│
├─ Try coin 1: 1 + helper(coins, 6-1=5)
│ │
│ helper(coins, 5)
│ ├─ Try coin 1: 1 + helper(coins, 4)
│ │ helper(coins, 4)
│ │ ├─ Try coin 1: 1 + helper(coins, 3)
│ │ │ helper(coins, 3)
│ │ │ ├─ Try coin 1: 1 + helper(coins, 2)
│ │ │ │ helper(coins, 2)
│ │ │ │ ├─ Try coin 1: 1 + helper(coins, 1)
│ │ │ │ │ helper(coins, 1)
│ │ │ │ │ └─ Try coin 1: 1 + helper(coins, 0)
│ │ │ │ │ return 0
│ │ │ │ │ return 1
│ │ │ │ ├─ Try coin 2: 1 + helper(coins, 0)
│ │ │ │ │ return 0
│ │ │ │ │ return 1 ✓
│ │ │ │ return min(2, 1) = 1
│ │ │ ├─ Try coin 2: 1 + helper(coins, 1)
│ │ │ │ return 1
│ │ │ │ Result: 1 + 1 = 2
│ │ │ return min(3, 2) = 2
│ │ ├─ Try coin 2: 1 + helper(coins, 2)
│ │ │ return 1
│ │ │ Result: 1 + 1 = 2
│ │ return min(4, 2) = 2
│ ├─ Try coin 2: 1 + helper(coins, 3)
│ │ return 2
│ │ Result: 1 + 2 = 3
│ ├─ Try coin 5: 1 + helper(coins, 0)
│ │ return 0
│ │ Result: 1 + 0 = 1 ✓
│ return min(6, 3, 1) = 1
│
│ Result from coin 1: 1 + 1 = 2 ✓
│
├─ Try coin 2: 1 + helper(coins, 4)
│ return 2
│ Result: 1 + 2 = 3
│
└─ Try coin 5: 1 + helper(coins, 1)
return 1
Result: 1 + 1 = 2 ✓
min(2, 3, 2) = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
The answer 2 can be achieved by:
6 = 1 + 5 (two coins)
6 = 5 + 1 (two coins)
Why This Is Slow:
Notice the recursion tree:
helper(5) is called MULTIPLE times!
helper(4) is called MULTIPLE times!
helper(3) is called MULTIPLE times!
Lots of repeated work! This is the problem!
For amount = 100, the tree would be GIGANTIC!
Many overlapping subproblems being solved over and over!
This is why brute force is TOO SLOW! ❌
📊 Complexity Analysis
Time Complexity: Exponential O(S^n)
S = amount
n = number of coins
At each level, we branch into n choices
Maximum depth is S (worst case using all 1's)
Total: n^S ≈ exponential
For amount = 100, coins = 3:
3^100 = astronomical!
WAY TOO SLOW! ❌
Space Complexity: O(S)
Recursion stack depth
In worst case (all 1's), depth = S
Why This Is Slow:
❌ Tries every possible combination
❌ Repeats same subproblems many times
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int coinChange(int[] coins, int amount)
What it represents:
Variables we track:
- memo[i] = Minimum coins needed to make amount i
- If memo[i] is computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results to avoid recomputation - Each subproblem solved only ONCE!
Key Understanding:
Brute force calls helper(5) many times
Memoization calls helper(5) ONCE, caches result
Example:
First time helper(5) called:
- Compute answer (1 coin: use 5)
- Store in memo[5] = 1
Next time helper(5) called:
- Check memo[5]
- Found! Return 1 immediately
- No recomputation! ✓
This saves MASSIVE amounts of work!
💡 Intuition
The smart idea: Remember what we've already solved!
Think of it like a student doing homework:
WITHOUT memoization (brute force):
Problem: "Make 5 cents"
Student: *solves from scratch*
Later, same problem: "Make 5 cents"
Student: *solves from scratch AGAIN* ❌
WITH memoization:
Problem: "Make 5 cents"
Student: *solves from scratch*
Student: *writes in notebook: "5 cents = 1 coin"*
Later, same problem: "Make 5 cents"
Student: *checks notebook*
Student: "It's 1 coin!" ✓
Student: *instant answer, no recalculation!*
The notebook is the memo array!
📝 Implementation
class Solution {
private int[] memo;
public int coinChange(int[] coins, int amount) {
memo = new int[amount + 1];
Arrays.fill(memo, -2); // -2 means not computed yet
int result = helper(coins, amount);
// If impossible, return -1
return result == Integer.MAX_VALUE ? -1 : result;
}
private int helper(int[] coins, int amount) {
// Base case: amount is 0, need 0 coins
if (amount == 0) return 0;
// Base case: amount is negative, impossible
if (amount < 0) return Integer.MAX_VALUE;
// Check memo (our notebook!)
if (memo[amount] != -2) {
return memo[amount];
}
int minCoins = Integer.MAX_VALUE;
// Try each coin
for (int coin : coins) {
// Recursive call (might hit memo!)
int result = helper(coins, amount - coin);
// If this path is valid
if (result != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, 1 + result);
}
}
// Save to memo before returning!
memo[amount] = minCoins;
return minCoins;
}
}
🔍 Detailed Dry Run: coins = [1, 2, 5], amount = 6
memo = [-2, -2, -2, -2, -2, -2, -2]
0 1 2 3 4 5 6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(coins, 6)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
amount = 6
memo[6] = -2 (not computed yet)
Try coin 1: 1 + helper(coins, 5)
┌─ CALL: helper(coins, 5)
│ amount = 5
│ memo[5] = -2 (not computed yet)
│
│ Try coin 1: 1 + helper(coins, 4)
│ ┌─ CALL: helper(coins, 4)
│ │ amount = 4
│ │ memo[4] = -2
│ │
│ │ Try coin 1: 1 + helper(coins, 3)
│ │ ┌─ CALL: helper(coins, 3)
│ │ │ amount = 3
│ │ │ memo[3] = -2
│ │ │
│ │ │ Try coin 1: 1 + helper(coins, 2)
│ │ │ ┌─ CALL: helper(coins, 2)
│ │ │ │ amount = 2
│ │ │ │ memo[2] = -2
│ │ │ │
│ │ │ │ Try coin 1: 1 + helper(coins, 1)
│ │ │ │ ┌─ CALL: helper(coins, 1)
│ │ │ │ │ amount = 1
│ │ │ │ │ memo[1] = -2
│ │ │ │ │
│ │ │ │ │ Try coin 1: 1 + helper(coins, 0)
│ │ │ │ │ return 0
│ │ │ │ │
│ │ │ │ │ minCoins = 1
│ │ │ │ │ memo[1] = 1 ✓
│ │ │ │ └─ return 1
│ │ │ │
│ │ │ │ Try coin 2: 1 + helper(coins, 0)
│ │ │ │ return 0
│ │ │ │
│ │ │ │ minCoins = min(1 + 1, 1 + 0) = 1
│ │ │ │ memo[2] = 1 ✓
│ │ │ └─ return 1
│ │ │
│ │ │ Try coin 2: 1 + helper(coins, 1)
│ │ │ amount = 1
│ │ │ memo[1] = 1 ← FOUND IN MEMO! ✓
│ │ │ return 1 (instant!)
│ │ │
│ │ │ minCoins = min(1 + 1, 1 + 1) = 2
│ │ │ memo[3] = 2 ✓
│ │ └─ return 2
│ │
│ │ Try coin 2: 1 + helper(coins, 2)
│ │ amount = 2
│ │ memo[2] = 1 ← FOUND IN MEMO! ✓
│ │ return 1 (instant!)
│ │
│ │ minCoins = min(1 + 2, 1 + 1) = 2
│ │ memo[4] = 2 ✓
│ └─ return 2
│
│ Try coin 2: 1 + helper(coins, 3)
│ amount = 3
│ memo[3] = 2 ← FOUND IN MEMO! ✓
│ return 2 (instant!)
│
│ Try coin 5: 1 + helper(coins, 0)
│ return 0
│
│ minCoins = min(1 + 2, 1 + 2, 1 + 0) = 1
│ memo[5] = 1 ✓
└─ return 1
After coin 1: 1 + 1 = 2 ✓
Try coin 2: 1 + helper(coins, 4)
amount = 4
memo[4] = 2 ← FOUND IN MEMO! ✓
return 2 (instant!)
After coin 2: 1 + 2 = 3
Try coin 5: 1 + helper(coins, 1)
amount = 1
memo[1] = 1 ← FOUND IN MEMO! ✓
return 1 (instant!)
After coin 5: 1 + 1 = 2 ✓
minCoins = min(2, 3, 2) = 2
memo[6] = 2 ✓
return 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo = [0, 1, 1, 2, 2, 1, 2]
0 1 2 3 4 5 6
Each value computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Notice: helper(1), helper(2), helper(3), helper(4)
all called MULTIPLE times
First call: computed and cached
Later calls: returned from memo instantly!
This is the power of memoization!
Why This Works:
KEY INSIGHT:
Each unique amount is solved ONCE
Result is cached in memo[amount]
Future calls return cached result instantly
Comparison:
Brute force: helper(5) computed multiple times
Memoization: helper(5) computed ONCE, cached
This transforms exponential → polynomial time!
📊 Complexity Analysis
Time Complexity: O(S × n)
S = amount
n = number of coins
S unique subproblems (0 to amount)
Each subproblem tries n coins
Each subproblem solved ONCE (cached!)
Total: S × n
For amount = 100, coins = 3:
100 × 3 = 300 operations
MUCH better than exponential! ✓
Space Complexity: O(S)
Memo array: O(S)
Recursion stack: O(S) in worst case
Total: O(S)
🟢 Approach 3: Bottom-Up DP (Iterative)
📐 Function Definition
Function Signature:
int coinChange(int[] coins, int amount)
What it represents:
DP Array:
- dp[i] = Minimum coins needed to make amount i
- Build from dp[0], dp[1], ..., up to dp[amount]
- Each value uses previous values!
Purpose: - Compute answers for 0, 1, 2, ..., amount in order - For each i, try all coins - Use previously computed dp values!
Key Understanding:
Bottom-up builds from smallest to largest:
dp[0] = 0 (base case: need 0 coins for 0 amount)
dp[1]: Try all coins, pick minimum
dp[2]: Try all coins, pick minimum
dp[3]: Try all coins, pick minimum
...
dp[amount]: Try all coins, pick minimum
Build up the solution incrementally!
💡 Intuition
The systematic idea: Build answers from bottom up, like stairs!
Think of it like filling a table:
TOP-DOWN (Memoization):
Start at amount (top)
Work backwards to 0 (bottom)
Cache results as you go
BOTTOM-UP (This approach):
Start at 0 (bottom)
Work upwards to amount (top)
Build on previous answers
Like building with blocks:
Start with dp[0] = 0 (foundation)
Build dp[1] using dp[0]
Build dp[2] using dp[0], dp[1]
Build dp[3] using dp[0], dp[1], dp[2]
...
Build dp[amount] using all previous!
Each level uses the levels below it!
📝 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 all to infinity (impossible initially)
Arrays.fill(dp, Integer.MAX_VALUE);
// Base case: need 0 coins to make 0
dp[0] = 0;
// Build up from 1 to amount
for (int i = 1; i <= amount; i++) {
// Try each coin
for (int coin : coins) {
// Can we use this coin?
if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {
// ═══════════════════════════════════════════════════
// BACKWARD DP: Look at previous value
// ═══════════════════════════════════════════════════
// To make i, use coin once
// Then need to make i - coin with remaining
// Remaining takes dp[i - coin] coins
// Total: 1 + dp[i - coin]
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
// If dp[amount] is still infinity, impossible
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
🔍 Detailed Dry Run: coins = [1, 2, 5], amount = 11
Initial state:
dp = [0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF]
0 1 2 3 4 5 6 7 8 9 10 11
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration: i = 1
━━━━━━━━━━━━━━━━━━━━
Coins: [1, 2, 5]
Try coin 1:
i >= 1? YES ✓
dp[1-1] != INF? dp[0] = 0 ✓
dp[1] = min(INF, 1 + dp[0])
= min(INF, 1 + 0)
= 1 ✓
Try coin 2:
i >= 2? NO (1 < 2)
Skip
Try coin 5:
i >= 5? NO (1 < 5)
Skip
dp[1] = 1
Iteration: i = 2
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
i >= 1? YES ✓
dp[2-1] != INF? dp[1] = 1 ✓
dp[2] = min(INF, 1 + dp[1])
= min(INF, 1 + 1)
= 2
Try coin 2:
i >= 2? YES ✓
dp[2-2] != INF? dp[0] = 0 ✓
dp[2] = min(2, 1 + dp[0])
= min(2, 1 + 0)
= 1 ✓
Try coin 5:
i >= 5? NO
Skip
dp[2] = 1 (using coin 2 is better!)
Iteration: i = 3
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[3] = min(INF, 1 + dp[2])
= min(INF, 1 + 1)
= 2
Try coin 2:
dp[3] = min(2, 1 + dp[1])
= min(2, 1 + 1)
= 2 ✓
Try coin 5:
Skip
dp[3] = 2
Iteration: i = 4
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[4] = min(INF, 1 + dp[3])
= min(INF, 1 + 2)
= 3
Try coin 2:
dp[4] = min(3, 1 + dp[2])
= min(3, 1 + 1)
= 2 ✓
Try coin 5:
Skip
dp[4] = 2
Iteration: i = 5
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[5] = min(INF, 1 + dp[4])
= min(INF, 1 + 2)
= 3
Try coin 2:
dp[5] = min(3, 1 + dp[3])
= min(3, 1 + 2)
= 3
Try coin 5:
i >= 5? YES ✓
dp[5-5] != INF? dp[0] = 0 ✓
dp[5] = min(3, 1 + dp[0])
= min(3, 1 + 0)
= 1 ✓
dp[5] = 1 (just use coin 5!)
Iteration: i = 6
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[6] = min(INF, 1 + dp[5])
= min(INF, 1 + 1)
= 2
Try coin 2:
dp[6] = min(2, 1 + dp[4])
= min(2, 1 + 2)
= 2 ✓
Try coin 5:
dp[6] = min(2, 1 + dp[1])
= min(2, 1 + 1)
= 2 ✓
dp[6] = 2
Iteration: i = 7
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[7] = min(INF, 1 + dp[6])
= 3
Try coin 2:
dp[7] = min(3, 1 + dp[5])
= min(3, 1 + 1)
= 2 ✓
Try coin 5:
dp[7] = min(2, 1 + dp[2])
= min(2, 1 + 1)
= 2 ✓
dp[7] = 2
Iteration: i = 8
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[8] = min(INF, 1 + dp[7])
= 3
Try coin 2:
dp[8] = min(3, 1 + dp[6])
= min(3, 1 + 2)
= 3
Try coin 5:
dp[8] = min(3, 1 + dp[3])
= min(3, 1 + 2)
= 3 ✓
dp[8] = 3
Iteration: i = 9
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[9] = min(INF, 1 + dp[8])
= 4
Try coin 2:
dp[9] = min(4, 1 + dp[7])
= min(4, 1 + 2)
= 3
Try coin 5:
dp[9] = min(3, 1 + dp[4])
= min(3, 1 + 2)
= 3 ✓
dp[9] = 3
Iteration: i = 10
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[10] = min(INF, 1 + dp[9])
= 4
Try coin 2:
dp[10] = min(4, 1 + dp[8])
= min(4, 1 + 3)
= 4
Try coin 5:
dp[10] = min(4, 1 + dp[5])
= min(4, 1 + 1)
= 2 ✓
dp[10] = 2 (use 5+5)
Iteration: i = 11 - FINAL
━━━━━━━━━━━━━━━━━━━━
Try coin 1:
dp[11] = min(INF, 1 + dp[10])
= min(INF, 1 + 2)
= 3
Try coin 2:
dp[11] = min(3, 1 + dp[9])
= min(3, 1 + 3)
= 3
Try coin 5:
dp[11] = min(3, 1 + dp[6])
= min(3, 1 + 2)
= 3 ✓
dp[11] = 3 (using 5+5+1 or 5+2+2+2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP ARRAY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
0 1 2 3 4 5 6 7 8 9 10 11
Verification:
dp[0] = 0 (base)
dp[1] = 1 (1)
dp[2] = 1 (2)
dp[3] = 2 (2+1)
dp[4] = 2 (2+2)
dp[5] = 1 (5)
dp[6] = 2 (5+1)
dp[7] = 2 (5+2)
dp[8] = 3 (5+2+1)
dp[9] = 3 (5+2+2)
dp[10] = 2 (5+5)
dp[11] = 3 (5+5+1) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ANSWER: 3 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works - Visual Understanding:
Think of it like Fibonacci:
Fibonacci:
fib[0] = 0
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2]
Compute fib[2], fib[3], ..., in order
Each uses previous values!
Coin Change:
dp[0] = 0
dp[i] = min(1 + dp[i-coin]) for all coins
Compute dp[1], dp[2], ..., in order
Each uses previous values!
SAME PATTERN - Build from bottom up! 🎯
📊 Complexity Analysis
Time Complexity: O(S × n)
S = amount
n = number of coins
Outer loop: S iterations (1 to amount)
Inner loop: n coins to try
Total: S × n
For amount = 10,000, coins = 12:
10,000 × 12 = 120,000 operations
Very manageable! ✓
Space Complexity: O(S)
DP array of size amount + 1
No recursion stack needed
Total: O(S)
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ COIN CHANGE - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ Exp │ O(S) │ High │ Start │
│ Memoization │ O(S×n) │ O(S) │ Good │ Good │
│ Bottom-Up DP │ O(S×n) │ O(S) │ Best ✓ │ Best ✓ │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
S = amount, n = number of coins
For interviews: Show progression from brute force to DP!
💻 Complete Working Code
class Solution {
public int coinChange(int[] coins, int amount) {
return dp(coins, amount);
}
// Approach 3: Bottom-Up DP - O(S×n) time, O(S) space
private int dp(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// Approach 2: Memoization - O(S×n) time, O(S) space
private int[] memo;
private int memoization(int[] coins, int amount) {
memo = new int[amount + 1];
Arrays.fill(memo, -2); // -2 = not computed
return helperMemo(coins, amount);
}
private int helperMemo(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return Integer.MAX_VALUE;
if (memo[amount] != -2) return memo[amount];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = helperMemo(coins, amount - coin);
if (result != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, 1 + result);
}
}
memo[amount] = minCoins;
return minCoins;
}
// Approach 1: Brute Force - Exponential time
private int bruteForce(int[] coins, int amount) {
int result = helperBrute(coins, amount);
return result == Integer.MAX_VALUE ? -1 : result;
}
private int helperBrute(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return Integer.MAX_VALUE;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = helperBrute(coins, amount - coin);
if (result != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, 1 + result);
}
}
return minCoins;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.coinChange(new int[] { 1, 2, 5 }, 11) == 3);
System.out.println(s.coinChange(new int[] { 2 }, 3) == -1);
System.out.println(s.coinChange(new int[] { 1 }, 0) == 0);
}
}
🔑 Key Insights
Why Greedy Fails:
Greedy doesn't always work!
Example: coins = [1, 3, 4], amount = 6
Greedy: 4+1+1 = 3 coins ✗
Optimal: 3+3 = 2 coins ✓
Must try ALL combinations to find minimum!
Pattern Recognition:
Classic UNBOUNDED KNAPSACK pattern!
Characteristics:
- Have items (coins)
- Can use each item UNLIMITED times
- Want to minimize/maximize something
Other problems with same pattern:
- Perfect Squares
- Rod Cutting
- Minimum Cost for Tickets
Why DP Works:
For each amount i, try using every coin:
dp[i] = min(1 + dp[i - coin])
Build from dp[0] to dp[amount]
Each value uses previous values
Classic bottom-up DP!
🎪 Memory Aid
"Try ALL coins, pick minimum!"
"Build from 0 to amount, use previous values!"
"Greedy fails - DP finds true optimal!"
"Unbounded Knapsack - use each item unlimited times!" ✨
⚠️ Common Mistakes
- ❌ Using greedy approach (doesn't work!)
- ❌ Forgetting base case dp[0] = 0
- ❌ Not checking if dp[i - coin] is valid
- ❌ Not handling impossible case (return -1)
- ❌ Integer overflow (use Integer.MAX_VALUE carefully)
✅ Interview Talking Points
"This is the classic Unbounded Knapsack problem.
Why greedy fails:
Example: coins=[1,3,4], amount=6
Greedy picks 4 first → 3 coins total
But optimal is 3+3 → 2 coins
Must try all combinations!
DP Approach:
dp[i] = minimum coins to make amount i
Base case: dp[0] = 0
For each i from 1 to amount:
Try every coin
dp[i] = min(1 + dp[i - coin])
If dp[amount] is still infinity → impossible → return -1
This is Unbounded Knapsack because:
- Each coin can be used unlimited times
- We want to minimize number of coins
Complexity: O(S×n) time, O(S) space
where S = amount, n = number of coins
Optimal solution!"
📝 Quick Revision Notes
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int coinChange(int[] coins, int k) {
// This is unbounded knapsack
// int res = recursive(coins, k);
// Integer[] memo = new Integer[k + 1];
// int res = topDown(coins, k, memo);
int res = bottomUp(coins, k);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int bottomUp(int[] coins, int k) {
int[] dp = new int[k + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// base case
dp[0] = 0;
// main concept in bottom up:
// you need to find result for every coin starting from 1 to k
// you are building up the results.
// so, every i becomes k in each loop (VERY IMP)
for (int i = 1; i <= k; i++) {
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
int temp = dp[i - coin];
if (temp != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], 1 + temp);
}
}
}
return dp[k] == Integer.MAX_VALUE ? -1 : dp[k];
}
private int topDown(int[] coins, int k, Integer[] memo) {
if (k == 0) {
return 0;
}
if (k < 0) {
return Integer.MAX_VALUE;
}
if (memo[k] != null) {
return memo[k];
}
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int temp = topDown(coins, k - coin, memo);
if (temp != Integer.MAX_VALUE) {
res = Math.min(res, 1 + temp);
}
}
return memo[k] = res;
}
private int recursive(int[] coins, int k) {
// step 3: base case 1 - if nothing left, return 0.
if (k == 0) {
return 0;
}
// step 4: base case 2 - if went -ve, do not consider this itself.
if (k < 0) {
return Integer.MAX_VALUE;
}
int res = Integer.MAX_VALUE;
// step 1: take 1 coin at a time
for (int coin : coins) {
// step 2: reduce the total amount by the coin taken.
int temp = recursive(coins, k - coin);
if (temp != Integer.MAX_VALUE) {
res = Math.min(res, 1 + temp);
}
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.coinChange(new int[] { 1, 2, 5 }, 11) == 3);
System.out.println(s.coinChange(new int[] { 2 }, 3) == -1);
System.out.println(s.coinChange(new int[] { 1 }, 0) == 0);
}
}
🎉 Congratulations!
You've mastered Coin Change - the canonical Unbounded Knapsack problem!
What You Learned:
✅ Why greedy fails - Must try all combinations
✅ Brute force approach - Try every coin recursively
✅ Memoization - Cache results to avoid recomputation
✅ Bottom-up DP - Build from 0 to amount systematically
✅ Unbounded Knapsack - Use items unlimited times
✅ O(S×n) solution - Efficient and optimal
This is THE classic DP problem that appears everywhere! 🚀✨