Dynamic programming · stretch

Fewest coins

Write min_coins(coins, amount) returning the fewest coins that add up to amount, using each coin value as many times as you like, or -1 if it cannot be done.

Taking the biggest coin first does not always work: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 but 3 + 3 is better. Build a list best where best[a] is the answer for amount a, from 0 upwards.

right answers
arguments left as they should be

def min_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

Run adds print(min_coins([1, 3, 4], 6)) after your code, to try it.

Stuck on the idea rather than the code? The Dynamic programming lesson walks through it.