DP: coin change

Given coin denominations and a target amount, what is the fewest coins that add up exactly to amount? You may use each denomination as many times as you like.

Grabbing the biggest coin first (a greedy strategy) can fail: for coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 is only 2. To always get it right we build up answers for every sub-amount from 0 to amount.

Let best[a] be the fewest coins to make a. The best way to make a is to use some coin c, then optimally make a - c:

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

We seed best[0] = 0 (zero coins make zero) and treat "impossible" as infinity.

Your task

Write coin_change(coins, amount) returning the minimum number of coins that sum to amount, or -1 if it cannot be done.

coin_change([1, 2, 5], 11)   # 3   -> 5 + 5 + 1
coin_change([2], 3)          # -1  -> odd amount, only even coins
coin_change([1], 0)          # 0

Hint: make a list best of size amount + 1 filled with a large sentinel, set best[0] = 0, then for each sub-amount try every coin and keep the smallest count. At the end, return -1 if best[amount] is still the sentinel.