class Solution:
    def coin_change(self, coins, amount):
        if amount < 1:
            return -1
        
        memo = [0 for _ in range(amount)]
        return self.helper(coins, amount, memo)
    
    def helper(self, coins, amount, memo):
        if amount < 0:
            return -1
        
        if amount == 0:
            return 0
        
        if memo[amount - 1]:
            return memo[amount - 1]
        
        min_count = float('inf')
        for coin in coins:
            res = self.helper(coins, amount - coin, memo)
            if res >= 0 and res < min_count:
                min_count = res
        
        memo[amount - 1] = -1 if min_count == float('inf') else 1 + min_count
        return memo[amount - 1]