class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:
        
        
        """
        Solution-1: Recurtsion with memory
        """

        # mem = {}

        
        # def helper(coins, amount) -> int:
                
        #     if amount in mem: return mem[amount]
            
        #     if amount == 0: 
        #         mem[amount] = 0
        #         return 0
            
        #     res = sys.maxsize - 1
            
        #     for coin in coins:
        #         if amount >= coin: 
        #             this_res = helper(coins, amount - coin)
        #             if this_res == -1: 
        #                 continue
        #             else:
        #                 res = min(res, this_res + 1)
            
        #     if res == sys.maxsize-1:
        #         mem[amount] = -1
        #         return -1
            
        #     mem[amount] = res
        #     return res
        
        # return helper(coins, amount)   



        """
        Solution-2: Dynamic Programming.
        """

        dp = [sys.maxsize-1] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            if dp[i] == sys.maxsize-1:
                continue
            for coin in coins:
                if coin + i <= amount:
                    dp[coin + i] = min(dp[coin+i], dp[i] + 1)
        if dp[-1] == sys.maxsize-1: return -1
        return dp[-1]