[322. Coin Change] #leetcode

322_1019.py

class Solution(object):
  # O(n) O(n)
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        # corner case
        if not coins:
            return -1
        if not amount:
            return 0
        
        # dp placeholder
        dp = [0] * (amount+1)
        
        for x in range(1, amount+1):
            # f(x) = min(f(x- ci)) + 1
            temp = [dp[x-c] for c in coins if x-c >= 0 and dp[x-c] != -1] 
            dp[x] = min(temp) + 1 if temp else -1
            
        return dp[amount]