| class Solution(object):
|
| def __init__(self):
|
| self.dp = {}
|
|
|
| def change(self, amount, coins):
|
| self.coins = sorted(coins)
|
| return self.find_total_ways(amount, self.coins)
|
|
|
| def find_total_ways(self, amount, coins):
|
| if (amount, tuple(coins)) in self.dp:
|
| return self.dp[(amount, tuple(coins))]
|
|
|
| if amount == 0:
|
| return 1
|
|
|
| res = 0
|
| for i in range(len(coins)):
|
| if coins[i] <= amount:
|
| res += self.find_total_ways(amount - coins[i], coins[i:])
|
|
|
| self.dp[(amount, tuple(coins))] = res
|
| return res
|