DFS + pruning beats 100% python


  • 1
    Y

    regular DFS
    the only difference is that in the dfs search start with
    picking special offer 2, we don't need to picking special offer 1 again as the combination would be already calculated.
    example:
    pick sp1,sp1,sp2 is the same as pick sp2, sp1, sp1

        def shoppingOffers(self, price, special, needs):
            """
            :type price: List[int]
            :type special: List[List[int]]
            :type needs: List[int]
            :rtype: int
            """
            self.res = sys.maxint
            self.dfs(needs,special,price,0,0)
            return self.res
            
        def dfs(self, needs, special, price, currentprice, specialindex):
            if needs == [ 0 for x in xrange(len(needs))]:
                self.res = min(self.res,currentprice)
                return
            for x in xrange(specialindex,len(special)):
                vaild = True
                for y in xrange(len(needs)):
                    if needs[y] < special[x][y]:
                        vaild = False
                        break
                if vaild == True:
                    nextneeds = [needs[a] - special[x][a] for a in xrange(len(needs))]
                    self.dfs(nextneeds,special,price,currentprice+special[x][-1],x)
            for z in xrange(len(needs)):
                if needs[z] >= 1:
                    currentprice += price[z]*needs[z]
            self.res = min(self.res,currentprice)
    

  • 0
    L

    Best Solution I have ever seen. Fcking awesome!


Log in to reply
 

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