DFS + pruning beats 100% python

  • 1

    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.
    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
            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)
            for x in xrange(specialindex,len(special)):
                vaild = True
                for y in xrange(len(needs)):
                    if needs[y] < special[x][y]:
                        vaild = False
                if vaild == True:
                    nextneeds = [needs[a] - special[x][a] for a in xrange(len(needs))]
            for z in xrange(len(needs)):
                if needs[z] >= 1:
                    currentprice += price[z]*needs[z]
            self.res = min(self.res,currentprice)

  • 0

    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.