These are the notes for DSA episode 64. A parcel needs ₹6 of postage and the counter has ₹1, ₹3 and ₹4 stamps. The clerk's habit, biggest stamp first, gives 4 + 1 + 1 = 3 stamps, but 3 + 3 needs only 2. We watch greedy fail live (3 instead of 2, and -1 for amount 6 with coins [2, 5] although 2 + 2 + 2 works), write the correct recursion (try every last coin: Time Limit Exceeded for amount 100), and build the DP table dp[a] = min over c of dp[a - c] + 1. Then Coin Change II counts the ways, where the order of the two loops decides whether we count combinations or orders. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.
The problem, in real life
| At the post office | In code |
|---|---|
| Stamp values ₹1, ₹3, ₹4 (plenty of each) | coins = {1, 3, 4} |
| Postage needed: ₹6 | amount = 6 |
| Fewest stamps | Coin Change (LeetCode 322) |
| Number of different stamp combinations | Coin Change II (LeetCode 518) |
With India's coins and notes (1, 2, 5, 10, 20, 50, …) biggest-first always gives the fewest; such coin systems are called canonical. With other sets (1, 3, 4) it can fail.
Every word, from zero
- Unbounded supply: each coin value can be used any number of times.
- Greedy (biggest first): take the largest coin that fits, repeat.
- Canonical coin system: one where greedy always gives the fewest coins.
- State:
dp[a]= fewest coins to make amounta(part 1), or the number of ways to makea(part 2). - Recurrence from the last coin: if the last coin is
c, the rest is amounta - c. - Sentinel ("impossible" marker): a value that can never be a real answer; here
amount + 1. - Combination vs permutation (order):
{1, 2, 2}counted once vs1+2+2,2+1+2,2+2+1counted separately. - Integer overflow:
Integer.MAX_VALUE + 1wraps toInteger.MIN_VALUE(−2,147,483,648).
Problem statement
LeetCode 322, Coin Change. Return the fewest coins that make up amount, or -1 if impossible.
| coins | amount | Answer |
|---|---|---|
[1, 2, 5] |
11 | 3 (5 + 5 + 1) |
[2] |
3 | -1 |
[1] |
0 | 0 |
Constraints: 1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2^31 - 1, 0 ≤ amount ≤ 10^4.
Greedy fails: biggest coin first
import java.util.*;
public class Main {
static int coinChange(int[] coins, int amount) {
int[] c = coins.clone();
Arrays.sort(c);
int count = 0;
for (int i = c.length - 1; i >= 0; i--)
while (amount >= c[i]) {
amount -= c[i];
count++;
}
return amount == 0 ? count : -1;
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{1, 2, 5}, 11));
System.out.println(coinChange(new int[]{2}, 3));
System.out.println(coinChange(new int[]{1}, 0));
System.out.println(coinChange(new int[]{1, 3, 4}, 6));
System.out.println(coinChange(new int[]{2, 5}, 6));
}
}
3
-1
0
3
-1
[1, 3, 4], 6 → greedy 3 (4+1+1), best 2 (3+3). [2, 5], 6 → greedy takes 5 and is stuck at 1: -1, but 2 + 2 + 2 works.
Obvious correct idea: try every last coin
import java.util.*;
public class Main {
static int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int best = -1;
for (int c : coins)
if (c <= amount) {
int sub = coinChange(coins, amount - c);
if (sub != -1 && (best == -1 || sub + 1 < best)) best = sub + 1;
}
return best;
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{1, 2, 5}, 11));
System.out.println(coinChange(new int[]{2}, 3));
System.out.println(coinChange(new int[]{1}, 0));
System.out.println(coinChange(new int[]{1, 3, 4}, 6));
}
}
3
-1
0
2
Amount 100 with [1, 2, 5]: Time Limit Exceeded. Every amount branches three ways, the depth can reach 100, and the same smaller amounts are solved over and over.
The key insight: the DP table
- State:
dp[a]= fewest coins for amounta. - Recurrence:
dp[a] = min over coins c ≤ a of dp[a - c] + 1. - Base:
dp[0] = 0; every other cell starts atamount + 1= impossible (you never need more thanamountcoins, even with ₹1 coins). - Order:
a = 1 … amount; answer-1ifdp[amount] > amount.
By hand, stamps [1, 3, 4], amount 6:
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| dp[a] | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1) = min(3, 2, 3) = 2.
Solution in Java: fewest coins
import java.util.*;
public class Main {
static 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];
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{1, 2, 5}, 11));
System.out.println(coinChange(new int[]{2}, 3));
System.out.println(coinChange(new int[]{1}, 0));
System.out.println(coinChange(new int[]{1, 3, 4}, 6));
System.out.println(coinChange(new int[]{2, 5}, 6));
System.out.println(coinChange(new int[]{1, 2, 5}, 100));
System.out.println(coinChange(new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}, 10000));
System.out.println(coinChange(new int[]{7, 13}, 9999));
}
}
3
-1
0
2
3
20
5
771
(c <= a also protects against huge coin values like 2^31 - 1: they're never subtracted.)
Top-down: the recursion plus a notebook
-1 is a real answer (impossible), so -2 marks "not known yet".
import java.util.*;
public class Main {
static int[] memo;
static int coinChange(int[] coins, int amount) {
memo = new int[amount + 1];
Arrays.fill(memo, -2);
return fewest(coins, amount);
}
static int fewest(int[] coins, int amount) {
if (amount == 0) return 0;
if (memo[amount] != -2) return memo[amount];
int best = -1;
for (int c : coins)
if (c <= amount) {
int sub = fewest(coins, amount - c);
if (sub != -1 && (best == -1 || sub + 1 < best)) best = sub + 1;
}
memo[amount] = best;
return best;
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{1, 2, 5}, 11));
System.out.println(coinChange(new int[]{2}, 3));
System.out.println(coinChange(new int[]{1}, 0));
long t0 = System.nanoTime();
int n = coinChange(new int[]{1, 2, 5}, 100);
System.out.println(n + " coins, " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
3
-1
0
20 coins, 0 ms
Which coins? Remember the last coin of every amount
import java.util.*;
public class Main {
static void plan(int[] coins, int amount) {
int[] dp = new int[amount + 1], last = 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 - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
last[a] = c;
}
List<Integer> used = new ArrayList<>();
for (int a = amount; a > 0; a -= last[a]) used.add(last[a]);
System.out.println(amount + " = " + used + ", " + dp[amount] + " coins");
}
public static void main(String[] args) {
plan(new int[]{1, 3, 4}, 6);
plan(new int[]{1, 3, 4}, 10);
plan(new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}, 2789);
}
}
6 = [3, 3], 2 coins
10 = [3, 3, 4], 3 coins
2789 = [2, 2, 5, 10, 20, 50, 200, 500, 2000], 9 coins
Part 2: Coin Change II (LeetCode 518), the number of ways
Return the number of combinations that make amount. dp[0] = 1 (the empty way).
| amount | coins | Answer |
|---|---|---|
| 5 | [1, 2, 5] |
4 (5 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1) |
| 3 | [2] |
0 |
| 10 | [10] |
1 |
Coins in the outer loop. Add one coin type at a time; each combination is built in one fixed order of coin types, so it's counted once:
| after coin | dp[0..5] |
|---|---|
| 1 | 1 1 1 1 1 1 |
| 2 | 1 1 2 2 3 3 |
| 5 | 1 1 2 2 3 4 |
import java.util.*;
public class Main {
static int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int c : coins)
for (int a = c; a <= amount; a++)
dp[a] += dp[a - c];
return dp[amount];
}
public static void main(String[] args) {
System.out.println(change(5, new int[]{1, 2, 5}));
System.out.println(change(3, new int[]{2}));
System.out.println(change(10, new int[]{10}));
System.out.println(change(500, new int[]{1, 2, 5, 10, 20, 50, 100, 200, 500}));
}
}
4
0
1
6295435
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// Coin Change (LeetCode 322): fewest coins. Coin Change II (LeetCode 518): number of combinations.
int coinChange(const vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
long long change(int amount, const vector<int>& coins) {
vector<long long> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins)
for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
return dp[amount];
}
int main() {
cout << coinChange({1, 2, 5}, 11) << " " << coinChange({2}, 3) << " " << coinChange({1}, 0) << " "
<< coinChange({1, 3, 4}, 6) << " " << coinChange({2, 5}, 6) << "\n";
cout << change(5, {1, 2, 5}) << " " << change(3, {2}) << " " << change(10, {10}) << "\n";
}
3 -1 0 2 3
4 0 1
The same solutions in Python
# Coin Change (LeetCode 322) and Coin Change II (LeetCode 518).
def coin_change(coins, amount):
dp = [0] + [amount + 1] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] > amount else dp[amount]
def change(amount, coins):
dp = [1] + [0] * amount
for c in coins: # coins outside: combinations
for a in range(c, amount + 1):
dp[a] += dp[a - c]
return dp[amount]
print(coin_change([1, 2, 5], 11), coin_change([2], 3), coin_change([1], 0), coin_change([1, 3, 4], 6), coin_change([2, 5], 6))
print(change(5, [1, 2, 5]), change(3, [2]), change(10, [10]))
3 -1 0 2 3
4 0 1
Coin change is an unbounded knapsack
Every coin can be reused, which is why the inner loop runs upward (a = c … amount): dp[a - c] may already include coin c. If each item could be used only once, that's the 0/1 knapsack (next episode), where the loop direction changes.
Three real bugs
Bug 1: Integer.MAX_VALUE as "impossible"
Arrays.fill(dp, Integer.MAX_VALUE); on [2], amount 3:
-2147483648
dp[1] is MAX_VALUE, and dp[1] + 1 overflows to the most negative int, which then wins every min. Use amount + 1.
Bug 2: the loops swapped (amounts outside)
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] += dp[a - c];
9
9 instead of 4: now 1+2+2, 2+1+2 and 2+2+1 are different. That counts orders, which is a different problem: Combination Sum IV (LeetCode 377).
Bug 3: no "impossible" check
return dp[amount]; on [2], amount 3:
4
4 is the sentinel amount + 1 leaking out; LeetCode wants -1.
Complexity
k = number of coin values.
| Approach | Time | Space | Big input |
|---|---|---|---|
| Biggest first | O(k log k + answer) | O(k) | wrong on some coin sets |
| Try every last coin | exponential | O(amount) stack | amount 100: Time Limit Exceeded |
| DP fewest coins | O(amount · k) | O(amount) | amount 10,000: 3 ms |
| DP number of ways | O(amount · k) | O(amount) |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Biggest coin first | 3 instead of 2; -1 instead of 3 |
greedy fails on non-canonical coins | DP over amounts |
Fill with Integer.MAX_VALUE |
-2147483648 |
MAX_VALUE + 1 overflows |
amount + 1 |
| Ways with amounts outside | 9 instead of 4 |
counts orders | coins in the outer loop |
| No impossible check | 4 instead of -1 |
the sentinel leaks out | > amount ? -1 : dp[amount] |
dp[0] = 0 in the ways problem |
every answer 0 |
nothing to build from | dp[0] = 1 |
int for many ways |
overflow on big amounts | counts grow fast | long (LeetCode 518 fits in int) |
Mini project: which coins?
Remember the last coin used for each amount, then walk back from amount.
import java.util.*;
public class Main {
// Mini project: fewest coins AND which coins, by remembering the last coin for every amount.
public static void main(String[] args) {
int[] coins = {1, 3, 4};
int amount = 10;
int[] dp = new int[amount + 1], last = 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 - c] + 1 < dp[a]) { dp[a] = dp[a - c] + 1; last[a] = c; }
List<Integer> used = new ArrayList<>();
for (int a = amount; a > 0; a -= last[a]) used.add(last[a]);
System.out.println("₹" + amount + " = " + used + " (" + dp[amount] + " stamps)");
}
}
₹10 = [3, 3, 4] (3 stamps)
Practice
1. Perfect Squares (LeetCode 279). The fewest perfect squares (1, 4, 9, 16, …) that sum to n.
Solution
Coin change where the coins are the squares up to n.
# Perfect Squares (LeetCode 279): coin change with square coins.
def num_squares(n):
squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
dp = [0] + [n + 1] * n
for a in range(1, n + 1):
for s in squares:
if s > a:
break
dp[a] = min(dp[a], dp[a - s] + 1)
return dp[n]
print(num_squares(12), num_squares(13), num_squares(1), num_squares(7))
3 2 1 4
2. Combination Sum IV (LeetCode 377). The number of ordered sequences that sum to target.
Solution
Exactly bug 2: amounts in the outer loop.
import java.util.*;
public class Main {
// Combination Sum IV (LeetCode 377): counts orders, so amounts go in the outer loop.
static int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int a = 1; a <= target; a++)
for (int x : nums)
if (x <= a) dp[a] += dp[a - x];
return dp[target];
}
public static void main(String[] args) {
System.out.println(combinationSum4(new int[]{1, 2, 3}, 4));
System.out.println(combinationSum4(new int[]{9}, 3));
}
}
7
0
3. Minimum Cost For Tickets (LeetCode 983). 1-day, 7-day and 30-day passes; cover all travel days for the least money. Hint: dp[d] = cheapest up to day d; on a travel day, min(dp[d-1] + c1, dp[d-7] + c7, dp[d-30] + c30).
Quick quiz
coins = [1, 5, 6, 9], amount = 11. Fewest coins? A) 2 B) 3 C) 4 D) -1
Answer
A) 2: 5 + 6. Biggest first takes 9 + 1 + 1 = 3.
Interview questions
- Why does greedy fail for coin change? Some coin systems aren't canonical: taking the biggest coin can force many small ones later (
[1, 3, 4], 6). - State and recurrence?
dp[a] = min over c ≤ a of dp[a - c] + 1,dp[0] = 0. - Why
amount + 1as infinity? It's larger than any real answer and doesn't overflow when you add 1. - Combinations vs permutations in the ways problem? Coins outside → combinations (518); amounts outside → orders (377).
- Complexity? O(amount × k) time, O(amount) space.
- How is this related to knapsack? It's the unbounded knapsack: each item can be reused. Next episode: each item at most once (0/1 knapsack).
Glossary
| Term | Meaning |
|---|---|
| Unbounded supply | Each coin can be used any number of times |
| Greedy (biggest first) | Take the largest coin that fits |
| Canonical coin system | Greedy always gives the fewest coins |
| State | dp[a] = fewest coins / number of ways for amount a |
| Sentinel | A value meaning "impossible" (amount + 1) |
| Combination | Order doesn't matter |
| Permutation (order) | Order matters |
| Integer overflow | Past Integer.MAX_VALUE, an int wraps to negative |
| Unbounded knapsack | Items reusable; coin change is one |
Summary
- Biggest-first change-giving fails on some coin sets (
[1, 3, 4], 6 → 3 instead of 2). - Fewest coins:
dp[a] = min(dp[a - c] + 1),dp[0] = 0, impossible =amount + 1, answer-1if still impossible. - Number of ways:
dp[0] = 1,dp[a] += dp[a - c], coins in the outer loop for combinations. - Both are O(amount × k). Watch for
MAX_VALUE + 1, swapped loops and the missing-1. - Next episode: 0/1 knapsack: each item can be used only once.