Shopping Offers
Medium · Backtracking · about 25 minutes
Asked at Google, Airbnb, Amazon.
price[i] is the price of item i, special[j] is an offer: the first n values are item quantities and the last is its price, and needs[i] is how many of item i you must buy (exactly — not more). Offers can be used any number of times. Return the lowest cost.