375.Guess Number Higher or Lower II

Tags: [recursion], [DP], [game], [min_max]

Link: https://leetcode.com/problems/guess-number-higher-or-lower-ii/#/description

We are playing the Guess Game. The game is as follows:

I pick a number from1ton. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay$x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: Recursion, DP, Game, Min Max

class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1:
            raise ValueError('The input is invalid')

        memo = [[-1 for _ in xrange(n + 1)] for _ in xrange(n + 1)]
        return self.solve(1, n, memo)

    def solve(self, start, end, memo):
        # base case
        if start >= end:
            return 0

        if memo[start][end] >= 0:
            return memo[start][end]

        min_payment = sys.maxint
        for elem in xrange(start, end + 1):
            min_payment = min(min_payment, 
                              max(self.solve(start, elem - 1, memo), 
                                  self.solve(elem + 1, end, memo)) + elem)

        memo[start][end] = min_payment
        return min_payment

Revelation:

• Actually, this question is asking that what is the payment if you follow the best strategy, and finally win the game. For example, n = 3, elems = [1, 2, 3], your best strategy should be that first choose the second element, the worst case is that the second element is not the target, then the game will tell you the target is less than or greater than the second element, so you know the answer, and finally you just need pay $2.
• Apply the DP (Dynamic Programming) to reduce the time complexity.
• Explanation the body of the recursion: Think about the current level recursion is our turn to play the game, so we should try our best to reduce the payment, which is why we try all possible elements in the current range and find the min payment. But the next turn is the other gamer, and we should assume that guy also does his best, following the best strategy. So we assume in this current turn (our turn) we didn't get the target, and we choose the max return value from the next turn (the other guy's turn) (because we assume that guy tries his best, following the best strategy).

Note:

• Time complexity = O(n^2), n is the given input. Think about that we need to fill the memo, which is a two dimensional matrix, so the time complexity is O(n^2).