Coin Change

一道总被拿来讲的DP题，思路上和LIS属于同一个套路，只是需要注意初始数组必须用sys.maxint而不是用0，这里考虑[0,1,1,1,8] 9 这个test case就行

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