LC 0322 [M] Coin Change (min coins to make amount)

for coin problems, remember to loop through the denoms, and think about the case not to take when the denom exceeds (or equals) the index

each coin we add we +1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        T = [float('inf')] * (amount + 1)
        
        T[0] = 0 # making amount = 0 counts as 0 coins used, not -1

        for denom in coins:
          for i in range(1, amount + 1):
            r = i - denom # remaining
            if r == 0:
              T[i] = 1
              continue
            elif r < 0: # can't make that amount (denom > i)
              continue
            else:
              if T[r] < T[i]:
                T[i] = T[r] + 1
            
        return T[-1] if T[-1] != float('inf') else -1

    def short(self, coins: List[int], amount: int) -> int:
        T = [float('inf')] * (amount + 1)
        
        T[0] = 0

        for denom in coins:
          for i in range(1, amount + 1):
            if denom < i:
              T[i] = min(T[i], T[i - denom] + 1)
            
        return T[-1] if T[-1] != float('inf') else -1