-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0322 [M] Coin Change (min coins to make amount)
Code with Senpai edited this page Dec 28, 2020
·
15 revisions
for coin problems, remember to loop through the denoms, and think about the case not to take when the denom exceeds (or equals) the index
each coin we add we +1
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
T = [float('inf')] * (amount + 1)
T[0] = 0 # making amount = 0 counts as 0 coins used, not -1
for denom in coins:
for i in range(1, amount + 1):
r = i - denom # remaining amount if we took this denom
if r == 0:
T[i] = 1
continue
elif r < 0: # can't make that amount (denom > i)
continue
else:
if T[r] < T[i]:
T[i] = T[r] + 1
return T[-1] if T[-1] != float('inf') else -1
def short(self, coins: List[int], amount: int) -> int:
T = [math.inf] * (amount + 1)
T[0] = 0
for denom in coins:
for amt in range(1, amount + 1):
if denom < amt:
T[amt] = min(T[amt], T[amt-denom] + 1)
return T[-1] if T[-1] != math.inf else -1
class Solution():
def coinChange(self, coins, amount):
coins.sort()
memo = {0: 0}
def minCoinsToMake(amount):
if amount in memo: return memo[amount]
minCoins = math.inf
for denom in coins:
if amount - denom < 0: break # or just continue if unsorted
includeCoin = minCoinsToMake(amount - denom) + 1
minCoins = min(minCoins, includeCoin)
memo[amount] = minCoins
return minCoins
res = minCoinsToMake(amount)
if res == math.inf: return -1
return res
footer