1
# Runtime: 164 ms (Top 43.73%) | Memory: 14 MB (Top 84.10%)
2
class Solution:
3
    def shoppingOffers(
4
        self, price: List[int], special: List[List[int]], needs: List[int]
5
    ) -> int:
6
        def dfs(price, special, needs, memo={}):
7
            if tuple(needs) in memo:
8
                return memo[tuple(needs)]
9
            res = [
10
                sum([p * need for p, need in zip(price, needs)])
11
            ]  # don't use any offer
12
            for offer in special:
13
                # check if can apply the offer
14
                new_needs = []
15
                for offer_items, need in zip(offer[:-1], needs):
16
                    new_needs.append(need - offer_items)
17
                if min(new_needs) < 0:
18
                    continue
19
                # Check if without the offer is better
20
                value = 0
21
                for p, offer_items in zip(price, offer[:-1]):
22
                    value += p * offer_items
23
                if value < offer[-1]:
24
                    continue
25
                # Valid Case
26
                res.append(dfs(price, special, new_needs, memo) + offer[-1])
27
            memo[tuple(needs)] = min(res)
28
            return min(res)
29

30
        return dfs(price, special, needs)