Python DFS solution


  • 3
    F

    Just recursively try every possible combination.
    Compare how much it costs among retail price (no offer) and using each offer.
    Terminate when
    (1) The condition met: return accumulated value
    (2) The condition violated: not an option, hence infinity

    def shoppingOffers(self, price, special, needs):
            def dfs(remain, acc):
                if all(x == 0 for x in remain):
                    return acc
                elif any(x < 0 for x in remain):
                    return float('inf')
                ans = sum(map(lambda x, y: x*y, remain, price))
                for spc in special:
                    ans = min(ans, dfs(map(lambda x, y: x-y, remain, spc[:-1]), spc[-1]))                
                return ans+acc
            return dfs(needs, 0)
    

  • 0
    A

    Neat solution, thank you!


  • 1

    The testcases are weak. This solution TLEs on this case:
    [6,6,6,6,6,6]
    [[1,0,0,0,0,0,0],[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,1,0,0],[0,0,0,0,0,1,0]]
    [6,6,6,6,6,6]


Log in to reply
 

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