Definition
- Minimum coin change – find the fewest coins from given denominations to make an exact amount, with unlimited supply.
- State –
dp[a]is the minimum coins to form amounta. - Initialisation –
dp[0] = 0and all other slots set toamount + 1as a sentinel for unreachable. - Recurrence –
dp[a] = min(dp[a], 1 + dp[a - coin])for each coin that fits. - Unreachable – if
dp[amount]remains the sentinel, return -1. - Complexity – O(amount * denominations) time and O(amount) space.
The cash dispenser at the National Bank of India must hand out a requested amount using as few notes as possible, keeping the dispenser efficient and the customer's wallet tidy. The machine tries every denomination for each remaining amount and picks the combination that uses the fewest notes.
Understanding the Concepts
What is the minimum coin change problem?
Given a set of coin denominations and a target amount, find the minimum number of coins needed to make exactly that amount. Each denomination can be used unlimited times. If the amount cannot be made with the given denominations, return -1.
This is the minimisation variant of the Unbounded Knapsack pattern. Instead of maximising value, we minimise count. Instead of a profit, each coin contributes a count of one.
package com.bank.dsa;
import java.util.Arrays;
public class MinCoinChange {
public static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // sentinel: impossibly high
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) {
dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
System.out.println(minCoins(new int[]{1, 5, 10, 25}, 30)); // 2
System.out.println(minCoins(new int[]{2}, 3)); // -1
}
}
2
-1
Why does greedy fail for this problem?
The greedy approach always picks the largest coin that fits. This works for standard currency denominations like {1, 5, 10, 25} but fails for arbitrary sets. With coins {1, 3, 4} and amount 6, greedy picks 4 + 1 + 1 = three coins, but the optimal is 3 + 3 = two coins.
package com.bank.dsa;
public class GreedyVsDpCoins {
public static int greedy(int[] coins, int amount) {
java.util.Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0 && amount > 0; i--) {
while (coins[i] <= amount) {
amount -= coins[i];
count++;
}
}
return amount == 0 ? count : -1;
}
public static void main(String[] args) {
int[] coins = {1, 3, 4};
System.out.println("Greedy for 6: " + greedy(coins, 6)); // 3
System.out.println("DP for 6: " + MinCoinChange.minCoins(coins, 6)); // 2
}
}
Greedy for 6: 3
DP for 6: 2
How does the DP table work internally?
The array dp has (amount + 1) slots. dp[0] is zero because zero amount needs zero coins. Every other slot starts at the sentinel value (amount + 1), which is larger than any possible real answer because the maximum coins needed is at most the amount itself (using coins of value 1).
For each amount from 1 to the target, we try each denomination. If the coin fits (coin <= a), we check whether using one coin of that denomination plus the best way to make the remainder is better than what we already have.
After filling, if dp[amount] is still the sentinel, the amount cannot be formed from the given denominations.
package com.bank.dsa;
import java.util.Arrays;
public class MinCoinChangeTrace {
public static void trace(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int[] lastCoin = new int[amount + 1]; // which coin was used
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a && 1 + dp[a - coin] < dp[a]) {
dp[a] = 1 + dp[a - coin];
lastCoin[a] = coin;
}
}
}
if (dp[amount] > amount) {
System.out.println("Cannot make " + amount);
return;
}
System.out.print("Min coins for " + amount + ": " + dp[amount] + " → ");
int a = amount;
while (a > 0) {
System.out.print(lastCoin[a] + " ");
a -= lastCoin[a];
}
System.out.println();
}
public static void main(String[] args) {
trace(new int[]{1, 5, 10, 25}, 30);
trace(new int[]{1, 3, 4}, 6);
}
}
Min coins for 30: 2 → 5 25 Min coins for 6: 2 → 3 3
How is this different from counting the number of ways?
| Aspect | Min coins (minimisation) | Count ways (counting) |
|---|---|---|
| Goal | Fewest coins to make amount | Number of distinct coin combinations |
| dp meaning | dp[a] = min coins for amount a | dp[a] = number of ways to make amount a |
| Transition | dp[a] = min(dp[a], 1 + dp[a - coin]) | dp[a] += dp[a - coin] |
| Init | dp[0] = 0, rest = sentinel | dp[0] = 1, rest = 0 |
| Loop order sensitivity | No (min is commutative) | Yes (items outer = combos, amount outer = perms) |
package com.bank.dsa;
public class CoinChangeCountWays {
public static int countWays(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1; // one way to make zero: use no coins
for (int coin : coins) { // coins outer: combinations (not permutations)
for (int a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
}
public static void main(String[] args) {
System.out.println("Ways to make 5 with {1,2,5}: " + countWays(new int[]{1, 2, 5}, 5));
}
}
Ways to make 5 with {1,2,5}: 4
What are common mistakes?
The most common mistake is initialising dp[0] to the sentinel instead of zero. This makes the recurrence unable to build any amount because the base case is wrong.
// WRONG: dp[0] = amount + 1 means nothing can build on the base
Arrays.fill(dp, amount + 1);
// dp[0] is also amount + 1, which is wrong
// CORRECT: dp[0] = 0, rest = sentinel
Arrays.fill(dp, amount + 1);
dp[0] = 0;
Another mistake is returning dp[amount] directly without checking the sentinel. If the amount is unreachable, dp[amount] contains the sentinel value, which is a large number, not -1.
What are the edge cases?
When the amount is zero, the answer is zero (no coins needed). When the denominations list is empty, the answer is -1 for any positive amount. When the only denomination is 1, the answer equals the amount.
package com.bank.dsa;
public class MinCoinEdgeCases {
public static void main(String[] args) {
System.out.println(MinCoinChange.minCoins(new int[]{1, 5}, 0)); // 0
System.out.println(MinCoinChange.minCoins(new int[]{}, 5)); // -1
System.out.println(MinCoinChange.minCoins(new int[]{1}, 7)); // 7
System.out.println(MinCoinChange.minCoins(new int[]{2}, 3)); // -1
}
}
0
-1
7
-1
When should you use this in banking?
At the National Bank of India, the cash dispenser uses this algorithm to hand out a requested amount using the fewest notes. Fewer notes mean less mechanical wear on the dispenser and fewer notes in the customer's wallet.
package com.bank.service;
import java.util.Arrays;
public class CashDispenser {
private static final int[] DENOMINATIONS = {100, 200, 500, 2000};
public static String dispense(int amount) {
int[] dp = new int[amount + 1];
int[] lastNote = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int note : DENOMINATIONS) {
if (note <= a && 1 + dp[a - note] < dp[a]) {
dp[a] = 1 + dp[a - note];
lastNote[a] = note;
}
}
}
if (dp[amount] > amount) return "Cannot dispense " + amount;
StringBuilder sb = new StringBuilder();
sb.append("Dispensing ").append(amount).append(" using ").append(dp[amount]).append(" notes: ");
int a = amount;
while (a > 0) {
sb.append(lastNote[a]).append(" ");
a -= lastNote[a];
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(dispense(3700));
System.out.println(dispense(800));
}
}
Dispensing 3700 using 3 notes: 200 500 2000
Not possible with denomination 100 note: Dispensing 800 using 2 notes: 200 200 ...
What should a senior engineer know?
A senior engineer should know that the sentinel value (amount + 1) is chosen because it is impossible to need more coins than the amount itself (the worst case is all coins of value 1). Using Integer.MAX_VALUE as a sentinel is risky because adding 1 to it causes integer overflow.
The problem connects to the theory of canonical coin systems. A coin system is canonical if greedy always gives the optimal answer. Standard currencies are canonical by design. For non-canonical systems, the DP is necessary.
For very large amounts, the DP table can be huge. In practice, cash dispensers have small denominations (5-10 values) and amounts capped at the machine's capacity, so the table is manageable.
Visual Overview
Minimum Coin Change DP: coins = {1, 3, 4}, amount = 6
─────────────────────────────────────────────────────
dp[]: 0 S S S S S S (S = sentinel = 7)
0 1 2 3 4 5 6
Fill dp[1]: try 1 → 1+dp[0]=1 → dp[1]=1
Fill dp[2]: try 1 → 1+dp[1]=2 → dp[2]=2
Fill dp[3]: try 1 → 1+dp[2]=3
try 3 → 1+dp[0]=1 → dp[3]=1
Fill dp[4]: try 1 → 1+dp[3]=2
try 3 → 1+dp[1]=2
try 4 → 1+dp[0]=1 → dp[4]=1
Fill dp[5]: try 1 → 1+dp[4]=2
try 3 → 1+dp[2]=3
try 4 → 1+dp[1]=2 → dp[5]=2
Fill dp[6]: try 1 → 1+dp[5]=3
try 3 → 1+dp[3]=2 → dp[6]=2 (3+3)
try 4 → 1+dp[2]=3
Answer: dp[6] = 2 coins (3 + 3)
Greedy would pick: 4 + 1 + 1 = 3 coins (wrong!)
Key Takeaway
Minimum Coin Change is the minimisation variant of the Unbounded Knapsack pattern. The DP array stores the fewest coins needed for each amount, initialised to a sentinel value larger than any real answer, except amount zero which needs zero coins. For each amount, you try every denomination that fits and take the minimum of the current value and one plus the best for the remaining amount.
The sentinel initialisation is what makes unreachable amounts detectable. If after filling the entire table the target slot still holds the sentinel, the amount cannot be formed from the given denominations and you return -1. The greedy approach of always picking the largest coin fails for arbitrary denomination sets, which is why the DP is necessary.
At the National Bank of India, the cash dispenser uses this algorithm to hand out a requested amount using the fewest notes. Fewer notes mean less mechanical wear and a better customer experience. The dispenser tracks which note was used at each amount to reconstruct the actual dispensing sequence.
The senior-level point is that the sentinel should be (amount + 1) rather than Integer.MAX_VALUE, because adding 1 to MAX_VALUE causes integer overflow. Understanding why greedy is unsafe for general denominations and how the sentinel makes unreachable amounts detectable is what shows real understanding of this problem.
Remember one sentence: fill each amount with the fewest coins by trying every denomination and taking one plus the best remainder, and return -1 if the sentinel survives.
---