Coin Change

medium
Unit 11 · Dynamic Programming I0/2 to milestone

Given coin denominations and an amount, find:

  1. min_coins(coins, amount): the fewest coins that make the amount exactly, or -1 if it's impossible.
  2. count_ways(coins, amount): the number of combinations (order doesn't matter) that make the amount.

Greedy ("always take the biggest coin") fails for coins like [1, 3, 4] and amount 6. Use dynamic programming over amounts 0..amount.

#dynamic-programming2 visible + 2 hidden tests
solution.py · Python 3.13
Loading editor…
Run your code to see results. ⌘↵ to run · ⌘⇧↵ to submit
Coin Change · TechGradify