'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    
    # T: O(S * n), S: O(S)
    def coinChange2(self, coins, amount):
        # dp[i]: minimum number of coins needed to make change for amount i
        dp = [0] + [float('inf')] * amount
        for i in range(1, amount+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)

        return dp[-1] if dp[-1] != float("inf") else -1 
    
    # DP
    def coinChange1(self, coins: List[int], amount: int) -> int:
        return self.helper1(coins, amount, [0]*amount)
    
    def helper1(self, coins, remainder, count):
        if remainder < 0: return -1
        if remainder == 0: return 0
        if count[remainder-1] !=  0: return count[remainder-1]
        min_ = float("inf")
        for coin in coins:
            res = self.helper1(coins, remainder-coin, count)
            if res >= 0 and res <= min_:
                min_ = 1 + res
        count[remainder-1] = min_ if min_ == float("inf") else -1
        return count[remainder-1]
        
    
    # brute force: try all 
    # T: O(S^n), S: O(n), n as number of coins used, S as amount
    def coinChange(self, coins: List[int], amount: int) -> int:
        return self.helper(0, coins, amount)

    def helper(self, idxCoin, coins, amount):
        if amount == 0:
            return 0
        if idxCoin < len(coins) and amount > 0:
            maxVal = int(amount/coins[idxCoin])
            minCost = float("inf")
            for x in range(maxVal+1):
                if amount >= x * coins[idxCoin]:
                    res = self.helper(idxCoin+1, coins, \
                                      amount - x*coins[idxCoin])
                    if res != -1:
                        minCost = min(minCost, res + x)
            return minCost if minCost != float("inf") else -1
        return -1
                    
        