Problem statement

https://leetcode.com/problems/shopping-offers/

Solution

Let n be number of items and m be number of offers, k is maximum number of items you need to buy (6 in our problem). Then we can use dfs with memorization (which we can say is multi-dimentional dp), where we have dfs(state, q). state is tuple of how many items of each time we need to but and q is current offer we consider: we can either try this offer or go to the next offer. When we out of offers, we evaluate all money we need to have to buy all the rest items without offers.

Complexity

We have O(k^n * m) number of states and to process one state we need O(n) time, so we have O(k^n * cdot mn) time complexity and the same memory complexity. This number not very big, given problem conditions but also it is quite loose bound.

Code

class Solution:
    def shoppingOffers(self, price, special, needs):
        n, m = len(price), len(special)
        
        @lru_cache(None)
        def dfs(state, q):
            if min(state) < 0:  return float("inf")
            if q == m: return sum([price[i]*state[i] for i in range(n)])
            
            spec = special[q]
            new_state = tuple([state[i]-spec[i] for i in range(n)])
            return min(dfs(new_state, q) + spec[-1], dfs(state, q+1))
        
        return dfs(tuple(needs),0)

Remark

It is possible to use dp on subsets I think, but at the moment I am not sure how exaclty.