Python Solution(DFS+ Map)


  • 1
    W
    def shoppingOffers(self, price, special, needs):
        dic = {}
        def dfs(tup):
            if tup in dic:
                return dic[tup]
            dic[tup] = sum(i*j for i,j in zip(tup, price))
            for sp in special:
                newtup = tuple(k-l for k,l in zip(tup, sp))
                if min(newtup) < 0:
                    continue
                dic[tup] = min(dic[tup], dfs(newtup) + sp[-1])
            return dic[tup]
        return dfs(tuple(needs))

Log in to reply
 

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