0518-coin-change-ii.py

classSolution:
defchange(self, amount: int, coins: List[int]) ->int:
# MEMOIZATION
# Time: O(n*m)
# Memory: O(n*m)
cache= {}

defdfs(i, a):
ifa==amount:
return1
ifa>amount:
return0
ifi==len(coins):
return0
if (i, a) incache:
returncache[(i, a)]

cache[(i, a)] =dfs(i, a+coins[i]) +dfs(i+1, a)
returncache[(i, a)]

returndfs(0, 0)

# DYNAMIC PROGRAMMING
# Time: O(n*m)
# Memory: O(n*m)
dp= [[0] * (len(coins) +1) foriinrange(amount+1)]
dp[0] = [1] * (len(coins) +1)
forainrange(1, amount+1):
foriinrange(len(coins) -1, -1, -1):
dp[a][i] =dp[a][i+1]
ifa-coins[i] >=0:
dp[a][i] +=dp[a-coins[i]][i]
returndp[amount][0]

# DYNAMIC PROGRAMMING
# Time: O(n*m)
# Memory: O(n) where n = amount
dp= [0] * (amount+1)
dp[0] =1
foriinrange(len(coins) -1, -1, -1):
nextDP= [0] * (amount+1)
nextDP[0] =1

forainrange(1, amount+1):
nextDP[a] =dp[a]
ifa-coins[i] >=0:
nextDP[a] +=nextDP[a-coins[i]]
dp=nextDP
returndp[amount]