Lesson 281
Coin Change
Minimum Coins · Bottom-Up DP
1:00Build the minimum-coins DP table from scratch, see why greedy fails on non-canonical coin sets, and learn the "count the ways" cousin that counts combinations instead.
By the end, you can
- Write the min-coins recurrence and explain what dp[a] stores.
- Trace the bottom-up table fill for a given coin set and amount.
- Reconstruct which coins were used by walking the dp table backward.
- Explain why greedy is insufficient for non-canonical coin sets and when it is safe.
- Derive the count-the-ways variant and explain the role of loop order in producing combinations vs permutations.
- State the time and space complexity of both variants.
Up next in String Algorithms, Advanced DP & Competitive Techniques
