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]