322. Coin Change
[Medium] “You are given coins of different denominations and a total amount of money. Find the fewest number of coins that you need to make up that amount (else return -1; can use as many of each coin as needed)."
Python3:
def coinChange(self, coins: List[int], amount: int) -> int:
res = [0] + [float('inf')] * amount
coins.sort()
for partial in range(1, amount + 1):
to_try = [float('inf')]
for coin in coins:
if (partial - coin) < 0:
break
else:
to_try.append(res[partial - coin])
res[partial] = min(to_try) + 1
return res[amount] if res[amount] != float('inf') else -1