Python DP solution 289 ms


  • 0
    G

    '''

    class Solution(object):
        _memo={}
        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
                ret=hi*hi
                for i in range(hi-1, (hi+lo)/2-1, -1):
                    ret=min(ret, i+max(helper(lo,i-1), helper(i+1,hi)))
                self._memo[(lo,hi)]=ret
                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.