Python DFS + DP

  • 0
    class Solution(object):
        def shoppingOffers(self, price, special, needs):
            dp = dict()
            return self.dfs(price, special, needs, dp)
        def dfs(self, price, special, needs, dp):
            key = tuple(needs)
            if key in dp:
                return dp[key]
            ans = float('inf')
            for sale in special:
                if self.valid(sale, needs):
                    new_needs = [needs[i] - sale[i] for i in range(len(needs))]
                    ans = min(ans, self.dfs(price, special, new_needs, dp) + sale[-1])
            ans = min(ans, sum([needs[i] * price[i] for i in range(len(needs))]))
            dp[key] = ans
            return ans
        def valid(self, sale, needs):
            return all([needs[i] >= sale[i] for i in range(len(needs))])

Log in to reply

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