Участник:Никита Плетнев/shopping offers

Материал из DISCOPAL
Перейти к: навигация, поиск

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

class Solution:
    def bestCost(self, price, special, needs, history):
        needs_imm = tuple(needs)
        if needs_imm in history:
            return history[needs_imm]
        result = sum([pr * need for pr, need in zip(price, needs)])
        for offer in special:
            if all(need >= ofer for need, ofer in zip(needs, offer)):
                new_needs = [need - ofer for need, ofer in zip(needs, offer)]
                new_result = offer[-1] + self.bestCost(price, special, new_needs, history)
                if new_result < result:
                    result = new_result
        history[needs_imm] = result
        return result
 
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        history = {}
        return self.bestCost(price, special, needs, history)