Leetcode 638 Solution

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        if not price:
            return 0

        self.cache = {}

        def dfs(price, specials, needs):
            if sum([need for need in needs]) == 0:
                return 0

            key = tuple(needs)
            if key in self.cache:
                return self.cache[key]

            ans = sum([p * need for p, need in zip(price, needs)])

            for special in specials:
                if any(special[i] > needs[i] for i in range(len(needs))):
                    continue

                for i in range(len(needs)):
                    needs[i] -= special[i]
                ans = min(ans, dfs(price, specials, needs) + special[-1])
                for i in range(len(needs)):
                    needs[i] += special[i]

            self.cache[key] = ans
            return ans

        return dfs(price, special, needs)