Untitled

class Solution:
  # n: num of cards
  # m: total cost
  def giftCards(self, cardsCount, totalCost):
    mem = {} # (targetCost, leftCardsCount, denomStart)
    return self.dfsHelper(totalCost, [10, 30, 50], 0, cardsCount, mem)
    
  def dfsHelper(self, targetCost, denoms, denomStart, leftCardsCount, mem):
    if (targetCost, leftCardsCount, denomStart) in mem:
      return mem[(targetCost, leftCardsCount, denomStart)]
    # base case
    if targetCost == 0 and leftCardsCount == 0:
      return 1
    elif targetCost < 0 or leftCardsCount <= 0:
      return 0
    # general case
    totalWays = 0
    for i in range(denomStart, len(denoms)):
      ways = self.dfsHelper(targetCost - denoms[i], denoms, i, leftCardsCount - 1, mem)
      totalWays += ways
    mem[(targetCost, leftCardsCount, denomStart)] = totalWays
    return totalWays