DSA-130 · Unbounded minimum-cost dynamic programming
Coin Change — Minimum Coins
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 1992 deterministic checks. Learner drafts are not executed.
Understand the problem
Given positive integer coin denominations and a nonnegative amount, return the minimum number of coins whose values sum exactly to amount. You may use each denomination any number of times. Return -1 if the amount is impossible.
- coins is a non-null int[] of 0–100 denominations, each from 1 to 10,000. amount is from 0 to 10,000. Invalid values (including zero or negative denominations) are outside the contract and are not checked by the method.
- Return 0 for amount=0, even with no denominations; return -1 when no exact representation exists. Duplicate denominations are allowed and do not change the answer.
- Do not modify coins. Return the minimum count only, not the number of combinations or a witness. The recursive baseline is educational and only run on bounded small inputs.
Examples
Input:
coins=[1,2,5], amount=11
Output:35+5+1 uses three coins. Two coins total at most ten, so three is optimal.
Input:
coins=[1,3,4], amount=6
Output:23+3 beats the largest-first greedy result 4+1+1, which uses three coins.
Input:
coins=[2], amount=3
Output:-1No sum of 2-valued coins equals 3.
Input:
coins=[], amount=0
Output:0The empty selection is a valid exact sum of zero.
Before you start
- Optimal substructure and repeated subproblems
- Array base cases and unreachable sentinels
- Why a locally largest coin can be suboptimal
Recognize the structure
A solution has a last coin c, leaving the same minimum-count problem for amount-c. The same remainders recur, and each denomination can be reused. This is not 0/1 knapsack, and minimum count is not the combination-counting recurrence.
Try before revealing
Hint 1
Suppose you knew the final coin in an optimal solution. What smaller problem remains?
Hint 2
Store the best result for every smaller amount. Which state is definitely reachable before using any coin?
Hint 3
Set dp[0]=0 and other states to amount+1; fill increasing amounts using min(dp[value-coin]+1).
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate the last coin recursively
For amount 0, return 0. For a positive remainder, try every coin no larger than it, recursively solve the remainder, and take the least successful count plus one. For coins [1,3,4] and amount 6, branches include 1+best(5), 3+best(3), and 4+best(2). best(2) and other suffixes repeat. Positive coins guarantee termination. The search has at most m branches and depth at most A; a conservative bound is O((m+1)^(A+1)) time with O(A) stack space. This is deliberately limited to small cases in verification, not offered as a viable solution for amount 10,000.
Improve the baseline
Name a state sentence
dp[value] means the minimum number of coins needed to sum exactly to value, or unreachable. The index is the amount already solved, not a coin index or number of combinations.
Choose base and sentinel
dp[0]=0. Initialize other entries to amount+1 because any reachable amount uses at most amount positive-valued coins. Under the bounded contract, adding 1 cannot overflow an int.
Evaluate dependencies first
For value from 1 through amount, consider every coin<=value and minimize dp[value-coin]+1. Because coins are positive, every dependency has a smaller index and is final. Increasing amounts permit unlimited reuse.
Translate unreachable
Return -1 only if dp[amount] still equals the sentinel. Do not expose the internal sentinel as an answer.
Why it is correct
Base
The empty choice forms amount 0 with zero coins, and no negative number of coins is possible.
Inductive step
Assume every smaller amount has its optimal count or is correctly unreachable. Any solution for value has a last coin c and a solution for value-c. Replacing that suffix by a better suffix would improve the whole solution, so an optimum is represented by 1+dp[value-c]. Conversely every reachable candidate constructs a valid solution. Taking the minimum over all eligible last coins yields exactly the optimum.
Termination
Increasing value visits each state once and each state examines finitely many denominations. When value=amount is finished, the induction establishes the result. If all predecessors are unreachable or ineligible, the sentinel remains and no solution exists.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
public final class Solution {
public static int coinChange(int[] coins, int amount) {
int unreachable = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, unreachable);
dp[0] = 0;
for (int value = 1; value <= amount; value++) {
for (int coin : coins) {
if (coin <= value) dp[value] = Math.min(dp[value], dp[value - coin] + 1);
}
}
return dp[amount] == unreachable ? -1 : dp[amount];
}
public static int baseline(int[] coins, int amount) {
if (amount == 0) return 0;
int best = amount + 1;
for (int coin : coins) {
if (coin > amount) continue;
int suffix = baseline(coins, amount - coin);
if (suffix >= 0) best = Math.min(best, suffix + 1);
}
return best == amount + 1 ? -1 : best;
}
}
Read the meaningful blocks
Allocate and initialize
Arrays.fill sets every state unreachable; dp[0]=0 is essential. The sentinel is chosen from the positive-coin contract, not Integer.MAX_VALUE.
Transition from smaller amounts
coin<=value keeps indices nonnegative. A sentinel predecessor plus one stays above the sentinel and therefore cannot incorrectly improve the state.
Return contract output
The internal unreachable value is converted to -1. The reference never changes the denominations array.
Complexity
Let A be amount and m the number of denominations, including duplicates. The table performs A×m candidate checks after O(A) initialization: O(A(m+1)) time and O(A) auxiliary storage. This handles m=0 explicitly.
This is pseudo-polynomial in the numeric amount rather than polynomial in its binary encoding length. Output is one int. The recursive baseline uses O(A) stack space and exponential time in general; its tests cap the amount to avoid misleading performance claims.
Exact-state walkthroughs
Reveal normal and boundary traces
Greedy counterexample
Input: {"coins":[1,3,4],"amount":6} · Result: 2
Step 1 of 21: Initialize the base state and unreachable sentinel.
Only amount zero is initially reachable.
- amount 00
- amount 1unreachable
- amount 2unreachable
- amount 3unreachable
- amount 4unreachable
- amount 5unreachable
- amount 6unreachable
States below the current amount are final. The current state becomes final only after all eligible last coins are checked.
| Variable | Value |
|---|---|
| dp | [0,7,7,7,7,7,7] |
| unreachable | 7 |
See the affected Java block
1 import java.util.Arrays; 2 3 public final class Solution { 4 public static int coinChange(int[] coins, int amount) { 5 int unreachable = amount + 1; 6 int[] dp = new int[amount + 1]; 7 Arrays.fill(dp, unreachable); 8 dp[0] = 0; 9 for (int value = 1; value <= amount; value++) { 10 for (int coin : coins) { 11 if (coin <= value) dp[value] = Math.min(dp[value], dp[value - coin] + 1); 12 } 13 } 14 return dp[amount] == unreachable ? -1 : dp[amount]; 15 } 16 17 public static int baseline(int[] coins, int amount) { 18 if (amount == 0) return 0; 19 int best = amount + 1; 20 for (int coin : coins) { 21 if (coin > amount) continue; 22 int suffix = baseline(coins, amount - coin); 23 if (suffix >= 0) best = Math.min(best, suffix + 1); 24 } 25 return best == amount + 1 ? -1 : best; 26 } 27 } 28
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize the base state and unreachable sentinel.
Only amount zero is initially reachable.
- dp
[0,7,7,7,7,7,7]- unreachable
7
- For amount 1, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
1- coin
1- predecessor
0- candidate
1- before
7- dp
[0,1,7,7,7,7,7]
- Finalize amount 1.
All eligible last coins have been considered for this amount.
- value
1- dp
[0,1,7,7,7,7,7]
- For amount 2, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
2- coin
1- predecessor
1- candidate
2- before
7- dp
[0,1,2,7,7,7,7]
- Finalize amount 2.
All eligible last coins have been considered for this amount.
- value
2- dp
[0,1,2,7,7,7,7]
- For amount 3, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
3- coin
1- predecessor
2- candidate
3- before
7- dp
[0,1,2,3,7,7,7]
- For amount 3, try last coin 3.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
3- coin
3- predecessor
0- candidate
1- before
3- dp
[0,1,2,1,7,7,7]
- Finalize amount 3.
All eligible last coins have been considered for this amount.
- value
3- dp
[0,1,2,1,7,7,7]
- For amount 4, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
4- coin
1- predecessor
3- candidate
2- before
7- dp
[0,1,2,1,2,7,7]
- For amount 4, try last coin 3.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
4- coin
3- predecessor
1- candidate
2- before
2- dp
[0,1,2,1,2,7,7]
- For amount 4, try last coin 4.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
4- coin
4- predecessor
0- candidate
1- before
2- dp
[0,1,2,1,1,7,7]
- Finalize amount 4.
All eligible last coins have been considered for this amount.
- value
4- dp
[0,1,2,1,1,7,7]
- For amount 5, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
5- coin
1- predecessor
4- candidate
2- before
7- dp
[0,1,2,1,1,2,7]
- For amount 5, try last coin 3.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
5- coin
3- predecessor
2- candidate
3- before
2- dp
[0,1,2,1,1,2,7]
- For amount 5, try last coin 4.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
5- coin
4- predecessor
1- candidate
2- before
2- dp
[0,1,2,1,1,2,7]
- Finalize amount 5.
All eligible last coins have been considered for this amount.
- value
5- dp
[0,1,2,1,1,2,7]
- For amount 6, try last coin 1.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
6- coin
1- predecessor
5- candidate
3- before
7- dp
[0,1,2,1,1,2,3]
- For amount 6, try last coin 3.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
6- coin
3- predecessor
3- candidate
2- before
3- dp
[0,1,2,1,1,2,2]
- For amount 6, try last coin 4.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
6- coin
4- predecessor
2- candidate
3- before
2- dp
[0,1,2,1,1,2,2]
- Finalize amount 6.
All eligible last coins have been considered for this amount.
- value
6- dp
[0,1,2,1,1,2,2]
- Return the contract result.
The result follows from the completed state and the declared contract.
- result
2
Impossible odd amount
Input: {"coins":[2],"amount":3} · Result: -1
Step 1 of 7: Initialize the base state and unreachable sentinel.
Only amount zero is initially reachable.
- amount 00
- amount 1unreachable
- amount 2unreachable
- amount 3unreachable
States below the current amount are final. The current state becomes final only after all eligible last coins are checked.
| Variable | Value |
|---|---|
| dp | [0,4,4,4] |
| unreachable | 4 |
See the affected Java block
1 import java.util.Arrays; 2 3 public final class Solution { 4 public static int coinChange(int[] coins, int amount) { 5 int unreachable = amount + 1; 6 int[] dp = new int[amount + 1]; 7 Arrays.fill(dp, unreachable); 8 dp[0] = 0; 9 for (int value = 1; value <= amount; value++) { 10 for (int coin : coins) { 11 if (coin <= value) dp[value] = Math.min(dp[value], dp[value - coin] + 1); 12 } 13 } 14 return dp[amount] == unreachable ? -1 : dp[amount]; 15 } 16 17 public static int baseline(int[] coins, int amount) { 18 if (amount == 0) return 0; 19 int best = amount + 1; 20 for (int coin : coins) { 21 if (coin > amount) continue; 22 int suffix = baseline(coins, amount - coin); 23 if (suffix >= 0) best = Math.min(best, suffix + 1); 24 } 25 return best == amount + 1 ? -1 : best; 26 } 27 } 28
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize the base state and unreachable sentinel.
Only amount zero is initially reachable.
- dp
[0,4,4,4]- unreachable
4
- Finalize amount 1.
All eligible last coins have been considered for this amount.
- value
1- dp
[0,4,4,4]
- For amount 2, try last coin 2.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
2- coin
2- predecessor
0- candidate
1- before
4- dp
[0,4,1,4]
- Finalize amount 2.
All eligible last coins have been considered for this amount.
- value
2- dp
[0,4,1,4]
- For amount 3, try last coin 2.
Smaller amount states are final; the current state is the best candidate considered so far.
- value
3- coin
2- predecessor
1- candidate
5- before
4- dp
[0,4,1,4]
- Finalize amount 3.
All eligible last coins have been considered for this amount.
- value
3- dp
[0,4,1,4]
- Return the contract result.
The result follows from the completed state and the declared contract.
- result
-1
Test the contract
Input:
coins=[], amount=7
Output:-1No eligible choice.
Input:
coins=[7], amount=0
Output:0Zero base.
Input:
coins=[2], amount=4
Output:2Unlimited reuse.
Input:
coins=[2,2,3], amount=7
Output:3Duplicates do not change optimum.
Input:
coins=[4,6], amount=7
Output:-1Parity obstruction.
Input:
coins=[10000], amount=10000
Output:1Upper amount boundary.
Common mistakes and counterexamples
Always take the largest coin
Counterexample: [1,3,4], amount=6: greedy uses 4+1+1.
Compare all eligible last coins; 3+3 is optimal.
Initialize every state to zero
Counterexample: [2], amount=3 can falsely appear reachable.
Only dp[0] is zero; positive amounts start unreachable.
Add one to Integer.MAX_VALUE
Counterexample: An unreachable predecessor can wrap to a negative value.
Use amount+1 under these bounds, or explicitly guard an infinite sentinel.
Use each denomination once
Counterexample: [2], amount=4 requires two copies of 2.
Increasing amount dependencies permit reuse; a descending 0/1 loop solves another problem.
Follow-ups
Return one optimal set of coins.
Store a chosen predecessor coin on each strict improvement. Walk backward from amount, subtracting that coin. Define a deterministic tie rule and keep impossible amounts distinct; reconstruction costs O(number of coins).
Count combinations instead of minimizing.
Change the state meaning and addition recurrence. Iterate denomination types on the outside and amounts increasing on the inside to count unordered combinations. Deduplicate denominations if duplicate values should not count as different types; choose a numeric overflow policy.
Each denomination is available only once.
Use 0/1 transitions, processing amounts downward for each coin so a coin cannot feed its own later state. State the meaning of duplicates as physical coins. The unbounded recurrence here would violate that constraint.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 118/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.