Coin Change: Fewest Coins
Hard · Algorithms
Greedy (always take the biggest coin) does not always work: with coins [1, 5, 6, 9] and amount 11, greedy gives 9 + 1 + 1 (3 coins) but 6 + 5 uses only 2.
Dynamic programming solves it. Let best[a] be the fewest coins that make amount a. Then best[0] = 0 and best[a] = 1 + min(best[a - coin]) over all coins that fit. Fill the table from 0 up to amount.
Write min_coins(coins, amount) that returns the fewest coins needed to make amount exactly, using each coin value as many times as you like. Return -1 if it is impossible. Coins are positive, 0 <= amount <= 10000.