Coin Change

序列动态规划，经典题了

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        coins.sort()
        dp = [0] * (amount + 1)
        for i in xrange(1, amount + 1):
            dp[i] = sys.maxint
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
                else:
                    break

        return dp[amount] if dp[amount] != sys.maxint else -1

另外还可以用BFS做，其实在某种程度上，BFS本质就是无备忘的动态规划罢了

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        queue = collections.deque([(0, 0)])
        result = sys.maxint
        checker = set()
        while queue:
            curAmount, count = queue.pop()
            if curAmount >= amount:
                if curAmount == amount:
                    result = min(result, count)
                continue

            for coin in coins:
                if coin + curAmount not in checker:
                    checker.add(coin + curAmount)
                    queue.appendleft((curAmount + coin, count + 1,))

        return result if result != sys.maxint else -1