# Python, Straightforward with Explanation

• For convenience, let's think in terms of `value`, the discount each special offer gives from the nominal price. (The values in this array are non-positive.)

Our goal is to minimize the sum of our discount. Our top-down dp function, `discount`, will do this. Suppose we are currently considering the ith special offer, and we have some order. We must use some legal number of this offer special[i]: if we use K of them, then we will get a discount of `K * value[i]`, and in turn this will specify the candidates for our dp.

Let's also memoize to reduce repeated work - there are up to 7^6 * 100 = about 11 million states, which will fit memory.

``````def shoppingOffers(self, price, special, needs):
def nominal_price(offer):
return sum(p * offer[i] for i, p in enumerate(price))

value = [offer.pop() - nominal_price(offer) for offer in special]

memo = {}
def discount(i, *order):
if i == len(special):
return 0
if (i, order) not in memo:
ans = discount(i+1, *order)
val = 0
cur_order = order[:]
while True:
cur_order = map(operator.sub, cur_order, special[i])
val += value[i]
if any(x < 0 for x in cur_order): break
ans = min(ans, val + discount(i+1, *cur_order))
memo[i, order] = ans
return memo[i, order]

return nominal_price(needs) + discount(0, *needs)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.