Coin Change — Bottom-Up Dynamic Programming
Build the minimum coins needed for each amount up to target using previously computed states.
Problem Statement
Given coin denominations and an amount, compute the minimum number of coins needed to make up that amount, or -1 if impossible.
Why This Problem Matters
- Classic unbounded knapsack variant; every interviewer expects a DP approach.
- Shows how to transform a recursive solution into bottom-up iteration for performance.
- Locks in the idea of sentinel values representing unreachable states.
Thought Process
Define dp state
dp[a] = minimum coins needed to reach amount a; initialise dp[0] = 0 and others to a high value.
Iterate over amounts
For each amount, check every coin; if coin <= a and dp[a - coin] is valid, update dp[a].
Return sentinel aware result
If dp[amount] remains INF, return -1; otherwise return dp[amount].
Step-by-Step Reasoning
- Initialise dp array length amount + 1 with amount + 1 as INF.
- Set dp[0] = 0.
- For a from 1..amount, iterate coins; dp[a] = min(dp[a], dp[a - coin] + 1).
- Return dp[amount] if reachable else -1.
Dry Run
coins = [1,2,5], amount = 11
dp builds to 3 using 5+5+1.
coins = [2], amount = 3
dp[3] stays INF so answer is -1.
Complexity Analysis
Time
O(amount · n)
Space
O(amount)
Why
Two nested loops over amount and coins with 1D state.
Annotated Solution
import java.util.Arrays;
public class CoinChange {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int current = 1; current <= amount; current += 1) {
for (int coin : coins) {
if (coin <= current) {
dp[current] = Math.min(dp[current], dp[current - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}Bottom-up DP avoids recursion depth issues and reuses previous solutions to build the next amount.
Common Pitfalls
- Using Integer.MAX_VALUE causes overflow when adding 1; choose amount + 1 as sentinel.
- Iterating coins outermost prevents reuse; amounts must be outer loop for standard DP.
- Forgetting to guard unreachable states leads to incorrect minimums.
Follow-Up Questions
- How would you reconstruct which coins were used?
- Can you solve the coin change combinations variant that counts ways instead?