Python Solution using MinMax Tree and Memoization


  • 0
    U

    Although problem statement was highly ambiguous but finally aced it.

    class Solution(object):
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            self.cache = []
            for _ in range(n + 1):
                self.cache.append([None] * (n + 1))
            
            return self.getAmount(1, n)
        
        def getAmount(self, low, high):
            
            if low >= high:
                return 0
                
            if self.cache[low][high] is not None:
                return self.cache[low][high]
            
            ans = sys.maxint
            i = low
            j = high
            while i <= j:
                ans = min(ans, i + max(self.getAmount(low, i - 1), self.getAmount(i + 1, high)))
                i += 1
            
            self.cache[low][high] = ans
            return ans
            
        
            
    

Log in to reply
 

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