Dynamic Programming · LC #322
Coin Change
Classic unbounded knapsack: fill a dp array where dp[a] = min coins to make amount a, trying every coin at every amount. Return -1 if unreachable.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given coin denominations and an `amount`, return the fewest number of coins needed to make up that amount, or -1 if it is not possible.
Sample I/O
Input: coins=[1,5,11], amount=15 Output: 3 (5+5+5) Input: coins=[2], amount=3 Output: -1
Intuition
How to Think About It
Intuition
DP works because the minimum coins for amount a is 1 + the minimum coins for a-coin, for any valid coin. Optimal substructure holds (sub-problems are non-overlapping in contribution) and overlapping sub-problems make tabulation far more efficient than recursion.
Core Concept
dp[a] = min over all coins c where c<=a of (dp[a-c] + 1). Initialise dp[0]=0, rest to amount+1 (infinity sentinel). If dp[amount] > amount, return -1.
When to use
Minimum-count selection from an unbounded supply - change-making, fewest stamps, minimum operations with fixed costs.
When NOT to use
When each denomination can only be used once → 0/1 knapsack; iterate j downward. When you need all combinations (not minimum) → different recurrence.
Key Insights
What to Know Cold
- Infinity sentinel amount+1 works because you can never need more than amount coins of value 1.
- Inner loop over coins (not over amounts) makes it unbounded - each coin can be reused.
- Outer loop over amounts ensures all sub-amounts are solved before they are referenced.
- BFS alternative: treat amount as a graph; each coin is an edge of weight 1 - BFS finds minimum.
- Coin Change 2 (LC 518) counts combinations not minimum - swap min with sum and loop order changes.
1 example
Worked Examples
Fewest coins for amount 11 from [1,5,6,9]
coins=[1,5,6,9], amount=11. Greedy fails (9+1+1=3 but 6+5=2).
Bottom-up DP table, O(amount × |coins|).
Output: 2
Demonstrates why greedy fails for general coin sets and why DP is necessary. Template for all unbounded-knapsack minimum-count problems.