Medium
Dynamic Programming
Coin Change
Fewest coins for amount = 1 + the best over amount minus each coin.
Approach
Build dp[0..amount] where dp[a] is the minimum coins to make a. For each amount, try every coin and take 1 + dp[a − coin], seeding dp[0] = 0 and everything else as infinity. The final dp[amount] is the answer, or −1 if unreachable.
Time complexity
O(amount · coins)
Space complexity
O(amount)
Common mistake
Using a greedy largest-coin-first approach — it fails for coin systems like [1, 3, 4] making 6.
See it run, step by step
Generate an interactive lesson for Coin Change — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Coin Change