Interview challenge · medium · dynamic-programming
Coin Change
El reto
El enunciado va en inglés, igual que en el vídeo.
Given a list of coin values and a target amount, return the fewest number of coins that make up that amount. You can use each coin as many times as you want. If the amount can't be made, return -1.
Example
coins [1, 2, 5], amount 11 -> 3 (5 + 5 + 1)
coins [2], amount 3 -> -1
coins [1], amount 0 -> 0Idea: dynamic programming from the bottom up. best[a] is the fewest coins for amount a: zero for 0, and for every other amount, one coin c plus the best way to make a - c. Fill the table from 1 to the amount and read the last cell. Time O(amount × coins), space O(amount).
La solución
# Coin Change - ayotl.dev
def coin_change(coins, amount):
INF = amount + 1
# best[a] = fewest coins that make a
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
n = best[a - c] + 1
best[a] = min(best[a], n)
b = best[amount]
return b if b < INF else -1
print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))
print(coin_change([1], 0))
$ python3 coin_change.py
3
-1
0