class Solution:
def change(self, amount: int, coins: List[int]) -> int:
memo = [[0 for _ in range(amount + 1)] for _ in range(amount + 1)]
def change(amount, coins, memo):
if amount == 0:
return 1
if amount < 0 or len(coins) == 0:
return 0
num = coins[-1]
target = amount - num
if memo[amount][num]:
return memo[amount][num]
a = change(target, coins, memo)
b = change(amount, coins[:-1], memo)
memo[amount][num] = a + b
return memo[amount][num]
return change(amount - coins[-1], coins, memo) + change(amount, coins[:-1], memo) |