LC 0322 [M] Coin Change (min coins to make amount) - ALawliet/algorithms GitHub Wiki
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
if we want to make 10 with 1,2,5, what is the min of making 10-1=9 (3), 10-2=8 (3), 10-5=5 (1)? choose 5 (1) then +1 to add the current coin = 2
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
amount +1 to include making 0
def short(self, coins: List[int], amount: int) -> int:
T = [math.inf] * (amount + 1)
T[0] = 0
for c in coins:
for a in range(c, amount + 1):
T[a] = min(T[a], T[a - c] + 1)
return T[-1] if T[-1] < math.inf else -1
def short(self, coins: List[int], amount: int) -> int:
n = amount
T = [math.inf] * (n+1)
T[0] = 0
for denom in coins:
for amt in range(1, n+1):
if amt - denom >= 0: # very important if ranging from 1!
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):
memo = {0: 0}
def minCoinsToMake(amt):
if amt in memo: return memo[amt]
minCoins = math.inf
for denom in coins:
if amt - denom >= 0:
minIfIncludeCoin = minCoinsToMake(amt - denom) + 1
minCoins = min(minCoins, minIfIncludeCoin)
memo[amt] = minCoins
return minCoins
res = minCoinsToMake(amount)
return res if res < math.inf else -1
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
@lru_cache(maxsize=amount)
def branch(amount):
min_count = sys.maxsize
if amount < 0: return -1
if amount == 0: return 0
for coin in coins:
count = branch(amount - coin)
if 0 <= count < min_count:
min_count = count + 1
return min_count if min_count < sys.maxsize else -1
return branch(amount)