Given coin values and an amount, find the fewest coins that add up to exactly that amount. You may use each coin as many times as you like.

fewest_coins([1, 5, 12], 15)  # 3
fewest_coins([5], 3)          # -1

Taking the biggest coin first fails here: 12 + 1 + 1 + 1 uses four coins, while 5 + 5 + 5 uses three.

Solve smaller amounts first and build on them. Let best[a] be the fewest coins for amount a. Then:

best[0] = 0
best[a] = 1 + min(
    best[a - c]
    for c in coins if c <= a)

Fill the table from 0 to the amount, using a large marker such as float("inf") for amounts that cannot be made, and turn it into -1 at the end.

Write fewest_coins(coins, amount) returning the smallest number of coins that sum to amount, or -1 if it cannot be done. An amount of 0 takes 0 coins.

The explanation opens here once every check passes.