Question

Formatted question description: https://leetcode.ca/all/375.html

We are playing the Guessing Game. The game will work as follows:

I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

Example 1:

Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is [8,10]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is [1,6]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is [4,6]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is [1,2]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

Constraints:

1 <= n <= 200

Algorithm

Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.

For this problem, create a two-dimensional dp array, where dp[i][j] represents the minimum amount of money needed to guess any number from i to j.

Then you need to traverse each interval [j, i], maintain a global minimum global_min variable, and then traverse every number in the interval to calculate the local maximum local_max = k + max(dp[j][k-1] , dp[k + 1][i]), this happens to divide the interval into two sections at each position, and then take the cost of the current position plus the larger cost of the two left and right sections as the local maximum value.

When k is 1, the left interval is empty, so cost is 0, and the right interval 2, 3, 4, according to the previous analysis, should be 3, so the entire cost is 1+3=4.

When k is 2, the left interval is 1, the cost is 0, the right interval is 3, 4, and the cost is 3. The entire cost is 2+3=5.

When k is 3, the left interval is 1, 2, the cost is 1, the right interval is 4, and the cost is 0, the entire cost is 3+1=4.

When k is 4, the left interval is 1, 2, 3, and the cost is 2, and the right interval is empty, and the cost is 0. The entire cost is 4+2=6.

To sum up all the cases of k, at this time, we should take the smallest overall cost, namely 4, as the final answer.

This is the minimax algorithm.

Code

public class Guess_Number_Higher_or_Lower_II {

    class Solution {
        public int getMoneyAmount(int n) {

            int[][] dp = new int[n + 1][n + 1];
            for (int i = 2; i <= n; ++i) {
                for (int j = i - 1; j > 0; --j) {
                    int global_min = Integer.MAX_VALUE;
                    for (int k = j + 1; k < i; ++k) {
                        int local_max = k + Math.max(dp[j][k - 1], dp[k + 1][i]);
                        global_min = Math.min(global_min, local_max);
                    }
                    dp[j][i] = (j + 1 == i ? j : global_min);
                }
            }
            return dp[1][n];

        }
    }
}

############

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 10][n + 10];
        for (int l = 2; l <= n; ++l) {
            for (int i = 1; i + l - 1 <= n; ++i) {
                int j = i + l - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j; ++k) {
                    int t = Math.max(dp[i][k - 1], dp[k + 1][j]) + k;
                    dp[i][j] = Math.min(dp[i][j], t);
                }
            }
        }
        return dp[1][n];
    }
}

// OJ: https://leetcode.com/problems/guess-number-higher-or-lower-ii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    int solve(vector<vector<int>> &dp, int i, int j) {
        if (i >= j) return 0;
        if (dp[i][j]) return dp[i][j];
        dp[i][j] = INT_MAX;
        for (int k = i; k <= j; ++k) dp[i][j] = min(dp[i][j], k + max(solve(dp, i, k - 1), solve(dp, k + 1, j)));
        return dp[i][j];
    }
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        return solve(dp, 1, n);
    }
};

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n + 10) for _ in range(n + 10)]
        for l in range(2, n + 1):
            for i in range(1, n - l + 2):
                j = i + l - 1
                dp[i][j] = inf
                for k in range(i, j + 1):
                    t = max(dp[i][k - 1], dp[k + 1][j]) + k
                    dp[i][j] = min(dp[i][j], t)
        return dp[1][n]

############

class Solution(object):
  def getMoneyAmount(self, n):
    """
    :type n: int
    :rtype: int
    """
    cache = [[0] * (n + 1) for _ in range(n + 1)]

    def dc(cache, start, end):
      if start >= end:
        return 0
      if cache[start][end] != 0:
        return cache[start][end]
      minV = float("inf")
      for i in range(start, end + 1):
        left = dc(cache, start, i - 1)
        right = dc(cache, i + 1, end)
        minV = min(minV, max(left, right) + i)
      if minV != float("inf"):
        cache[start][end] = minV
      return cache[start][end]

    dc(cache, 1, n)
    return cache[1][n]

func getMoneyAmount(n int) int {
	dp := make([][]int, n+10)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+10)
	}
	for l := 2; l <= n; l++ {
		for i := 1; i+l-1 <= n; i++ {
			j := i + l - 1
			dp[i][j] = math.MaxInt32
			for k := i; k <= j; k++ {
				t := max(dp[i][k-1], dp[k+1][j]) + k
				dp[i][j] = min(dp[i][j], t)
			}
		}
	}
	return dp[1][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

375 - Guess Number Higher or Lower II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions