Python, Straightforward with Explanation

  • 0

    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)

Log in to reply

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