Python DP solution 289 ms

  • 0


    class Solution(object):
        def getMoneyAmount(self, n):
            def helper(lo,hi):
                if (lo,hi) in self._memo: return self._memo[(lo,hi)]
                if hi-lo<=0: return 0
                for i in range(hi-1, (hi+lo)/2-1, -1):
                    ret=min(ret, i+max(helper(lo,i-1), helper(i+1,hi)))
                return ret
            return helper(1,n)

    To speed up the DP solution, first, I use memo; second, in the for loop, I used ''range(hi-1, (hi+lo)/2-1, -1)'' instead of ''range(hi-1, lo-1, -1)''.

Log in to reply

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