Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def coinChange(self, coins: List[int], amount: int) -> int:
- if len(coins) == 1:
- if amount % coins[0] == 0:
- return amount // coins[0]
- else:
- return -1
- elif amount == 0:
- return 0
- res = []
- ans = self.numCoins(coins, amount)
- return ans
- def numCoins(self, coins, amount, memo={}):
- if amount in memo:
- return memo[amount]
- if amount == 0:
- return 1
- elif amount < 0:
- return 0
- else:
- min_val = amount // min(coins)
- for coin in coins:
- if (amount - coin) >= 0:
- min_val = min(min_val, 1 + self.numCoins(coins, amount-coin, memo))
- memo[amount] = min_val
- return min_val
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement