class Solution(object):
    def coinChange(self, coins, amount, results=[0]*(10000)):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        :type 
        """
        minCoins = amount
        if amount in coins:
            results[amount] = 1
            return 1
        elif results[amount] > 0:
            return results[amount]
        else:
            for i in [c for c in coins if c <= amount]:
                numCoins = 1 + self.coinChange(coins, amount-i, results)
                if numCoins < minCoins:
                    minCoins = numCoins
                    results[amount] = minCoins
        if minCoins > len(coins):
            return -1
        return minCoins