Fewest Coins for an Amount
Problem
A machine pays out change using coin values from a given list, and it has an unlimited supply of every value. Return the smallest number of coins that add up to exactly amount, or -1 if no combination of coins reaches it. Coin values are positive and distinct, and an amount of 0 needs no coins at all.
Examples
Input: coins = [1, 4, 6], amount = 8
Output: 2
Why: 4 + 4; grabbing the 6 first leads to 6 + 1 + 1, three coinsInput: coins = [5, 10], amount = 3
Output: -1
Why: every coin is bigger than the amountInput: coins = [2], amount = 0
Output: 0
Why: edge case, nothing to payHints
0 / 3
Always taking the largest coin that fits feels natural, but the first example shows it can lose. You need to compare choices, not commit to one.
Whatever the last coin in an optimal answer is, the coins before it must themselves be an optimal answer for a smaller amount.
Build a table where entry a is the fewest coins for amount a, starting from entry 0 = 0. For each a from 1 upward, try every coin c no larger than a and take one plus entry a - c at its smallest. Unreachable amounts keep a value larger than any real answer.
Solution
Removing the last coin from an optimal payout leaves an optimal payout for a smaller amount, so the best count for amount a is one plus the best count for a minus some coin. Filling a table from 0 upward guarantees those smaller answers are ready when needed. Amounts that no coin mix can reach keep the sentinel amount + 1, which is more coins than any real answer could use, and that becomes -1 at the end. Time is O(amount times number of coins), and space is O(amount).
def fewest_coins(coins, amount):
NONE = amount + 1 # more coins than any real answer needs
best = [0] + [NONE] * amount # best[a] = fewest coins that make a
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1 # pay c last, the rest optimally
return best[amount] if best[amount] < NONE else -1
print(fewest_coins([1, 4, 6], 8)) # -> 2
print(fewest_coins([5, 10], 3)) # -> -1
print(fewest_coins([2], 0)) # -> 0Stuck on the idea rather than the code? Coin Change covers it.