Shopping Offers

Intuition

Solution

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        self.cache = {}
        self.price = price
        self.special = special
        return self.dfs(tuple(needs))

    def dfs(self, needs):
        if needs in self.cache:
            return self.cache[needs]
        total = 0
        for item in range(len(needs)):
            total += needs[item] * self.price[item]

        for spe in self.special:
            tmp = tuple([i - j for i, j in zip(needs, spe[:-1])])
            if min(tmp) < 0:
                continue
            total = min(total, self.dfs(tmp) + spe[-1])
        self.cache[needs] = total
        return total