Coin Change
Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given coins of different denominations and a total `amount`, return the fewest number of coins needed to make that amount. If it cannot be made from the given coins, return −1. You have an unlimited supply of each coin.
Constraints & assumptions
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ − 1
- 0 ≤ amount ≤ 10⁴
In plain English
You're a cashier making change and you want to hand over as few coins as possible. Grabbing the biggest coin first feels right, but it can backfire — with coins {1, 3, 4} making 6, greedy grabs 4+1+1 (three coins) when 3+3 (two coins) is better.
So instead you solve it from the bottom up. If you already know the fewest coins needed for every amount smaller than your target, the target is easy: try each coin, look up the best way to make the leftover, and add one for the coin you just used. Small answers stack into big ones — that's dynamic programming.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1Define best(a) = the fewest coins to make amount a.
- 2Base case: best(0) = 0. Any amount you can't build is −1 (or an 'infinity' sentinel).
- 3For amount a, try each coin ≤ a: best(a) = 1 + min over coins of best(a − coin).
- 4Answer is best(amount); if it's still the sentinel, return −1.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Fill a table from amount 0 up to the target.
We iteratively compute best(a) for every a from 1 to amount, using a sentinel (amount + 1) to mean 'unreachable'. No recursion — just a clean loop that guarantees each subproblem is solved before it's needed.
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // sentinel = "unreachable"
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) {
dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}