In LeetCode Store, there are some kinds of items to sell. Each item has a price.



However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.



You are given the each item's price, a set of special offers, and the number we need to buy for each item.
The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.



Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.


You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.



Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.



Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         def dfs(curr, special, needs):
             p=curr+sum(p*needs[i] for i,p in enumerate(price))
             for si in range(len(special)):
                 s = special[si]
                 if all(n>=s[i] for i,n in enumerate(needs)):
                     p=min(p, dfs(curr+s[-1], special[si:], [n-s[i] for i,n in enumerate(needs)]))
                 # else: p=min(p, dfs(curr, special[si+1:], needs))
             return p
         return dfs(0, special, needs)

class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         #用一个局部的最小值，每次更新
         def directPurchase(price,needs):
             total=0
             for i in range(len(needs)):
                 total+=price[i]*needs[i]
             return total
         #index表示对special offer遍历
         def dfs(price,special,needs,index):
             #一种在现实中有可能发生的情况：单独买可能比买套餐更加便宜
             local_min=directPurchase(price,needs)
             for i in range(index,len(special)):
                 offer=special[i]
                 temp=[]
                 #如果买了某种商品，则needs的数量一直更新,needs是个数组，所以需要遍历
                 for j in range(len(needs)):
                     #需要的比提供的少，不满足“刚好”的条件
                     if needs[j]<offer[j]:
                         #这一句很重要，不然会报错，只要有一种产品不满足条件，这一个special就都不能买
                         temp=[]
                         break
                     else:
                         #需要的更多
                         temp.append(needs[j]-offer[j])
                 #如果还有需要买的东西
                 if temp!=[]:
                     #动态规划的过程
                     local_min=min(local_min,offer[-1]+dfs(price,special,temp,i))
             return local_min
         return dfs(price,special,needs,0)
                         


class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         d = {}
         n = len(needs)
         
         def minp(needs,d):
             if str(needs) in d:
                 return d[str(needs)]
             res = 0
             for i in range(n):
                 res += price[i]*needs[i]
             for s in special:
                 for i in range(n):
                     if s[i]>needs[i]:
                         break
                 else:
                     need2 = []
                     for i in range(n):
                         need2.append(needs[i]-s[i])
                     res = min(res, minp(need2,d)+s[-1])
             d[str(needs)] = res
             return res
         
         return minp(needs,d)

class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         d = {}
         n = len(needs)
         
         def minp(needs,d):
             if str(needs) in d:
                 return d[str(needs)]
             res = 0
             for i in range(n):
                 res += price[i]*needs[i]
             for s in special:
                 need2 = []
                 for i in range(n):
                     if s[i]>needs[i]:
                         break
                     need2.append(needs[i]-s[i])
                 else:
                     res = min(res, minp(need2,d)+s[-1])
             d[str(needs)] = res
             return res
         
         return minp(needs,d)

class Solution:
     def shoppingOffers(self, rps,sos,tq):
         if len(sos)<1: return sum([x*y for x,y in zip(rps,tq)])
         so=sos.pop()
         m=self.shoppingOffers(rps,sos,tq)
         ss=so[:]
         while all([x<=y for x,y in zip(ss,tq)]):
             rq=[x-y for x,y in zip(tq,ss)]
             m=min(m,ss[-1]+self.shoppingOffers(rps,sos,rq))
             ss=[x+y for x,y in zip(ss,so)]
         sos.append(so)
         return m

class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         res = 0
         for pric, need in zip(price,needs):
             res += pric*need
         for offer in special:
             clone = list(needs)
             i=0
             while (i < len(needs)):
                 diff = clone[i] - offer[i]
                 if diff < 0:
                     break
                 clone[i] = diff
                 i+=1
             if i == len(needs):
                 res = min(res, offer[-1]+self.shoppingOffers(price,special,clone))
         return res
             


class Solution:
     def shoppingOffers(self, price, special, needs):
         a = 0
         n = len(needs)
         for i in range(n):
             a += needs[i] * price[i]
         
         
         for s in special:
             new_needs = needs.copy()
             check = True
             for i in range(n):
                 new_needs[i] = new_needs[i] - s[i]
                 if new_needs[i] < 0:
                     check = False
                     break
             
             if check:
                 a = min(a, s[n] + self.shoppingOffers(price, special, new_needs))
         return a


"""
 https://leetcode.com/problems/shopping-offers/description/
 """
 
 class Solution:
     def shoppingOffers(self, price, special, needs):
         """
         :type price: List[int]
         :type special: List[List[int]]
         :type needs: List[int]
         :rtype: int
         """
         number_of_items = len(price)
         states = {}
 
         for offer in special:
             offer_state = offer[0:number_of_items]
             offer_price = offer[-1]
 
             offer_state_key = self.convert_to_key(offer_state)
 
             if offer_state_key in states:
                 offer_price = min(offer_price, states[offer_state_key]["price"])
 
             states[offer_state_key] = {
                 "price": offer_price,
                 "state": offer_state
             }
 
         return self.compute_best_price(states, {}, needs, price)
 
     def convert_to_key(self, state):
         return "".join(str(i) for i in state)
 
     def compute_worst_price(self, needs, individual_prices):
         price = 0
         for i,v in enumerate(needs):
             price += needs[i] * individual_prices[i]
 
         return price
 
     def compute_best_price(self, original_offers, all_states, needs, individual_prices):
         if needs == [0] * len(needs):
             return 0
 
         needs_key = self.convert_to_key(needs)
 
         # If the state already exists - return
         if needs_key in all_states:
             return all_states[needs_key]["price"]
 
         # Compute
         best_price = self.compute_worst_price(needs, individual_prices)
         new_needs = []
         for offer_key in original_offers.keys():
             offer = original_offers[offer_key]
             valid_new_state = False
             new_needs = []
             for i, item_quantity in enumerate(offer["state"]):
                 quantity_left_for_item = needs[i] - item_quantity
 
                 if quantity_left_for_item < 0:
                     valid_new_state = False
                     break
                 else:
                     new_needs.append(quantity_left_for_item)
                     valid_new_state = True
 
             if valid_new_state:
                 new_price = offer["price"] + self.compute_best_price(original_offers, all_states, new_needs, individual_prices)
                 best_price = min(
                     best_price,
                     new_price
                 )
 
             # else just go to the next offer
 
         all_states[self.convert_to_key(new_needs)] = {
             "state": new_needs,
             "price": best_price
         }
 
         return best_price