Guess Number Higher or Lower II

Problem: Guess Number Higher or Lower II

We can use backtracking to go through all possible guessing and its cost. We can use memoization to reduce time cost.

Code in Python:

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