Dynamic Programming pattern
Coin Change
Given an array of coin denominations and a target amount, return the fewest number of coins needed to make up that amount. Each coin may be used unlimited times. If the amount cannot be made, return −1. Watch it run step by step, then write your own pseudocode and get it checked by AI.
- LeetCode 322
- Medium
- 2 approaches
Sign in with Google or GitHub and you land straight on this page. DSA comes with the all labs plan and every ChaiCode batch.
Dynamic ProgrammingLeetCode 322
Medium
From the first idea to the best one
- 01 Why greedy fails space
- 02 Optimized · bottom-up DP O(amount × #coins)O(amount) space
What you will learn
- How to read Coin Change and spot the dynamic programming pattern in it
- Why greedy fails: time, space
- Optimized · bottom-up DP: O(amount × #coins) time, O(amount) space
- The pseudocode for each approach, its line lit as the animation runs
- Practice: write your own pseudocode and get it checked
More Dynamic Programming
See Coin Change run, step by step
Sign in and this page opens on the animation, with all 18 Dynamic Programming problems beside it.
DSA comes with the all labs plan and every ChaiCode batch.