Coin Change: Minimum Coins
You'll learn how to find the fewest coins needed to make exact change using dynamic programming.
The Problem
Imagine you're a cashier with unlimited coins of certain denominations (like 1¢, 5¢, 10¢, 25¢). A customer needs exact change for a specific amount. What's the minimum number of coins you can use?
This is the Coin Change problem, and it's a classic application of dynamic programming that builds on the unbounded knapsack pattern.
Why Dynamic Programming?
This problem has optimal substructure: if you know the minimum coins for amount n-1, you can build the solution for n. It also has overlapping subproblems: calculating the answer for different amounts reuses smaller subproblem solutions.
The greedy approach (always picking the largest coin) doesn't always work. For coins [1, 3, 4] and amount 6, greedy gives 4+1+1 = 3 coins, but optimal is 3+3 = 2 coins.
The DP Approach
Define your state: dp[i] = minimum coins needed to make amount i.
Base case: dp[0] = 0 (zero coins for zero amount).
Transition: For each amount i, try using each coin c:
- If
c ≤ i, thendp[i] = min(dp[i], dp[i-c] + 1) - The
+1counts the coin you just used
This is "unbounded" because you can reuse the same coin denomination multiple times.
You build the table from amount 1 up to your target, considering all coin options at each step.
Key Takeaway: The Coin Change problem uses bottom-up DP to try each coin at every amount, tracking the minimum count by building on previously solved subproblems—a perfect example of optimal substructure with overlapping subproblems.