Coin Change

Problem: Coin Change

The fewest number of coins sum up to x can be get from minimum of fewest number of coins sum up to x-c plus 1, where c can be any coin change.

Code in Python:

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        MAX = float('inf')
        dp = [0] + [2**31] * amount

        for i in xrange(1, amount+1):
            dp[i] = min(dp[i-coin] if i-coin >= 0 else MAX for coin in coins) + 1

        return -1 if dp[amount] == MAX else dp[amount]s