Definition
Coin Change Minimum is a bottom-up Unbounded Knapsack optimization.
- DP array
dp[a]stores the minimum number of coins to make amounta. - Base case
dp[0] = 0because zero coins are needed for a zero amount. - Sentinel initializes all other entries to
amount + 1, a value larger than any possible answer. - Transition for each amount and each coin:
dp[a] = min(dp[a], dp[a - coin] + 1). - Answer is
dp[amount]if it is still the sentinel return -1, otherwise return it.
A teller at National Bank of India must hand out an exact amount using the fewest notes from available denominations. For each amount, the best (fewest notes) is one more than the best for the amount left after removing one note, tried across every denomination that fits.
Understanding the Concepts
What is the Coin Change Minimum Problem?
Given coin denominations and a target amount, return the fewest number of coins needed to make that amount. If the amount cannot be made by any combination of the coins, return -1. Each denomination can be used unlimited times.
At National Bank of India, an ATM must dispense an exact amount using the fewest notes from its loaded cassettes.
package com.bank.service;
public class CoinChangeMin {
public static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int sentinel = amount + 1; // larger than any valid answer
java.util.Arrays.fill(dp, sentinel);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
}
}
}
return dp[amount] >= sentinel ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] denominations = {1, 5, 10, 25};
System.out.println("Min coins for 30: " + minCoins(denominations, 30));
System.out.println("Min coins for 11: " + minCoins(denominations, 11));
}
}
Min coins for 30: 2
Min coins for 11: 2
Why Does Greedy Fail?
The greedy approach (always pick the largest coin that fits) fails for arbitrary denominations. For example, with coins [1, 3, 4] and amount 6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins. DP is required because it considers all possibilities.
package com.bank.core;
public class GreedyFails {
public static void main(String[] args) {
int[] coins = {1, 3, 4};
int amount = 6;
// Greedy: pick 4, then 1, then 1 = 3 coins
System.out.println("Greedy would use 3 coins: 4 + 1 + 1");
// DP: optimal is 3 + 3 = 2 coins
System.out.println("DP gives: " + CoinChangeMin.minCoins(coins, amount) + " coins");
}
}
Greedy would use 3 coins: 4 + 1 + 1
DP gives: 2 coins
How Does the DP Table Fill?
We initialize the array with a sentinel value (amount+1) and set dp[0]=0. For each amount from 1 to the target, we try every coin that fits and relax the minimum.
package com.bank.core;
public class CoinChangeTrace {
public static void main(String[] args) {
int[] coins = {1, 3, 4};
int amount = 6;
int[] dp = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
System.out.println("dp[" + a + "] = " + dp[a] + " (used coin " + coin + ")");
}
}
}
System.out.println("Answer: " + dp[amount]);
}
}
dp[1] = 1 (used coin 1)
dp[2] = 2 (used coin 1)
dp[3] = 1 (used coin 3)
dp[4] = 1 (used coin 4)
dp[5] = 2 (used coin 1)
dp[6] = 2 (used coin 3)
Answer: 2
How Is This Different from Coin Change Ways?
| Aspect | Coin Change Minimum | Coin Change Ways |
|---|---|---|
| Question | Fewest coins needed | Number of distinct combinations |
| DP value | Minimum count | Number of ways |
| Base case | dp[0] = 0 | dp[0] = 1 |
| Transition | min(dp[a], dp[a-coin]+1) | dp[a] += dp[a-coin] |
| Sentinel | amount+1 for unreachable | 0 (no ways) |
| Loop order | Either order works | Coins outside for combinations |
// Minimum: dp[a] = Math.min(dp[a], dp[a - coin] + 1)
// Ways: dp[a] += dp[a - coin]
What Are the Edge Cases?
Edge cases include: amount is zero (return 0), single coin equal to amount (return 1), and unreachable amount (return -1).
package com.bank.core;
public class CoinMinEdgeCases {
public static void main(String[] args) {
System.out.println(CoinChangeMin.minCoins(new int[]{1}, 0)); // 0
System.out.println(CoinChangeMin.minCoins(new int[]{5}, 5)); // 1
System.out.println(CoinChangeMin.minCoins(new int[]{2}, 3)); // -1
System.out.println(CoinChangeMin.minCoins(new int[]{3, 7}, 5)); // -1
}
}
0
1
-1
-1
What About Reconstructing Which Coins Were Used?
To know which coins were used, maintain a parallel array that records which coin was chosen at each amount.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class CoinChangeReconstruct {
public static List<Integer> reconstruct(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int[] chosen = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
chosen[a] = coin;
}
}
}
List<Integer> result = new ArrayList<>();
if (dp[amount] >= amount + 1) return result;
int remaining = amount;
while (remaining > 0) {
result.add(chosen[remaining]);
remaining -= chosen[remaining];
}
return result;
}
public static void main(String[] args) {
System.out.println("Coins used: " + reconstruct(new int[]{1, 3, 4}, 6));
}
}
Coins used: [3, 3]
Why Is the Sentinel amount+1 Instead of Integer.MAX_VALUE?
Using Integer.MAX_VALUE as the sentinel would cause integer overflow when adding 1 to it. Using amount + 1 is safe because the maximum number of coins to make any amount is at most amount (using all 1-valued coins), so amount + 1 is guaranteed larger than any valid answer.
// WRONG: Integer.MAX_VALUE + 1 overflows to Integer.MIN_VALUE
int sentinel = Integer.MAX_VALUE;
if (dp[a - coin] + 1 < dp[a]) // BUG: overflow!
// CORRECT: amount + 1 is safe
int sentinel = amount + 1;
if (dp[a - coin] + 1 < dp[a]) // safe comparison
What About Time and Space Complexity?
Time is O(amount * number of coins) because we iterate through all amounts and try all coins at each amount. Space is O(amount) for the DP array.
package com.bank.core;
public class CoinMinComplexity {
// Time: O(amount * coins) -> for each of amount values, try each coin
// Space: O(amount) -> single DP array
// This is the unbounded knapsack optimization variant
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Coin Change Ways: count combinations instead of finding the minimum.
- Which coins were used? Maintain a parallel array for reconstruction.
- Limited supply of each coin: bounded knapsack, need high-to-low sweep per coin.
- Can you solve it with BFS? Yes, each state is an amount, edges are coin values, and the shortest path gives the minimum coins.
package com.bank.core;
import java.util.LinkedList;
import java.util.Queue;
public class CoinChangeBFS {
public static int minCoinsBFS(int[] coins, int amount) {
if (amount == 0) return 0;
boolean[] visited = new boolean[amount + 1];
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited[0] = true;
int depth = 0;
while (!queue.isEmpty()) {
depth++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int curr = queue.poll();
for (int coin : coins) {
int next = curr + coin;
if (next == amount) return depth;
if (next < amount && !visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
}
return -1;
}
}
Visual Overview
Coin Change Minimum DP for coins [1, 3, 4], amount 6:
Index: 0 1 2 3 4 5 6
Init: [0, S, S, S, S, S, S] (S = sentinel = 7)
a=1: try coin 1 -> dp[1] = dp[0]+1 = 1
a=2: try coin 1 -> dp[2] = dp[1]+1 = 2
a=3: try coin 1 -> dp[3] = dp[2]+1 = 3
try coin 3 -> dp[3] = dp[0]+1 = 1 <- better!
a=4: try coin 1 -> dp[4] = dp[3]+1 = 2
try coin 4 -> dp[4] = dp[0]+1 = 1 <- better!
a=5: try coin 1 -> dp[5] = dp[4]+1 = 2
a=6: try coin 1 -> dp[6] = dp[5]+1 = 3
try coin 3 -> dp[6] = dp[3]+1 = 2 <- better!
Final: [0, 1, 2, 1, 1, 2, 2]
Answer: dp[6] = 2 (coins: 3 + 3)
Why greedy fails:
Greedy picks 4, then 1, then 1 = 3 coins
DP finds 3 + 3 = 2 coins
Key Takeaway
Coin Change for the minimum number of coins is a bottom-up dynamic programming problem. I define dp[a] as the fewest coins to make amount a, initialize every entry to a sentinel larger than any possible answer, and set dp[0] to zero because no coins are needed for a zero amount. Then for each amount from 1 to the target I try every coin that fits and relax the value to the minimum.
Iterating the amounts upward guarantees that dp[a-coin] is already final when I use it, and because the inner loop can pick the same denomination at every larger amount, coins are effectively unlimited. If dp[target] is still the sentinel at the end, the amount is unreachable and I return -1. The sentinel must be amount+1 rather than Integer.MAX_VALUE to avoid overflow when adding 1.
The critical interview point is that greedy (always pick the largest coin) fails for arbitrary denominations. With coins [1, 3, 4] and amount 6, greedy picks 4+1+1 for 3 coins, but DP finds 3+3 for 2 coins. This is exactly why DP is required.
In my project at National Bank of India, an ATM had to dispense an exact amount using the fewest notes from its loaded cassettes, and some amounts were impossible with the available denominations. I used this DP to always find the true minimum or correctly report that the amount cannot be dispensed.
Remember one sentence: dp[a] = min over all coins of dp[a-coin]+1, with a sentinel for unreachable amounts and greedy fails for arbitrary denominations.
---