[LeetCode] 322. Coin Change

Problem : https://leetcode.com/problems/coin-change/

Time Complexity = O ( M * N ),   M = amount,  N = len(coins).

Top-down Solution :

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        MAX_INT = 2 ** 31 - 1
        N = len(coins)
        coins.sort()
        
        @lru_cache(maxsize = None)
        def helper(amount):
            """
            Fewest number of coins needed
            to make up this amount.
            """
            if amount == 0:
                return 0
            
            result = MAX_INT
            
            for i in range(N):
                if coins[i] > amount:
                    break
                
                tmp = helper(amount - coins[i])
                if tmp != -1:
                    result = min(result, tmp + 1)
            
            return result if result != MAX_INT else -1
        
        
        return helper(amount)

Bottom-up Solution:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[n] = Fewest number of coins needed to make up amount n
        dp = [amount+1] * (amount + 1)
        dp[0] = 0
        
        coins.sort()
        
        for n in range(1, amount+1):
            for coin in coins:
                if coin > n:
                    break
                
                dp[n] = min(dp[n], dp[n-coin] + 1)
        
        return dp[-1] if dp[-1] != amount + 1 else -1