Coin Change: Number of Ways
You'll learn how to count all the distinct ways to make exact change for a target amount using unlimited coins of given denominations.
The Core Problem
Imagine you need to make exactly $5 using quarters (25¢), dimes (10¢), and nickels (5¢). How many different combinations can you use? You could use 20 nickels, or 10 nickels + 5 dimes, or 2 dimes + 3 nickels + 1 quarter, and so on.
Unlike the "Minimum Coins" variant (which finds the fewest coins needed), this problem asks: in how many distinct ways can we combine coins to reach our target?
Why Dynamic Programming?
This problem has both key DP properties:
-
Optimal substructure: To count ways to make amount
nwith coins[c1, c2, ...], we can break it down: ways using coinc1+ ways not usingc1. -
Overlapping subproblems: When counting ways to make 3, $2, etc.
The State and Transition
Define dp[amount][coin_index] = number of ways to make amount using only the first coin_index coin types.
Recurrence:
- If we don't use the current coin:
dp[amount][coin_index - 1] - If we do use it:
dp[amount - coin_value][coin_index](we can use it again!)
Sum both possibilities.
Base case: There's exactly 1 way to make amount 0 (use no coins).
Space-Optimized Approach
You can reduce to a 1D array: dp[i] = ways to make amount i. Process each coin and update all reachable amounts.
Key Takeaway: Count combinations by deciding whether to include/exclude each coin denomination, summing ways from overlapping subproblems using DP to avoid redundant calculations.