Why would this give me a TLE and this won't?


  • 0
    L

    So if you put the second if statement, checking if the tuple exists in the dictionary first, this will pass fine. However this fails, and I'm trying to figure out why since a check like if l>=r should be simple and there would never be a case in the dictionary where a tuple exists such that l>=r

    from collections import defaultdict
    class Solution(object):
        
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            self.dp=defaultdict(int)
            def helper(l,r):
                if l>=r: return 0
                if self.dp[(l,r)]: return self.dp[(l,r)]
                ret=min(x+max(helper(l,x-1),helper(x+1,r)) for x in range(l,r))
                self.dp[(l,r)]=ret
                #print self.dp
                return ret
            return helper(0,n)

Log in to reply
 

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