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