Advertisement
k4u5h4L

Leetcode coin change 2

Aug 4th, 2021
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.94 KB | None | 0 0
  1. class Solution:
  2.     def coinChange(self, coins: List[int], amount: int) -> int:
  3.         if len(coins) == 1:
  4.             if amount % coins[0] == 0:
  5.                 return amount // coins[0]
  6.             else:
  7.                 return -1
  8.         elif amount == 0:
  9.             return 0
  10.        
  11.         res = []
  12.            
  13.         ans = self.numCoins(coins, amount)
  14.                
  15.         return ans
  16.    
  17.     def numCoins(self, coins, amount, memo={}):
  18.         if amount in memo:
  19.             return memo[amount]
  20.         if amount == 0:
  21.             return 1
  22.         elif amount < 0:
  23.             return 0
  24.         else:
  25.             min_val = amount // min(coins)
  26.            
  27.             for coin in coins:
  28.                 if (amount - coin) >= 0:
  29.                     min_val = min(min_val, 1 + self.numCoins(coins, amount-coin, memo))
  30.                    
  31.             memo[amount] = min_val
  32.                
  33.             return min_val
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement