Question
Formatted question description: https://leetcode.ca/all/375.html
375 Guess Number Higher or Lower II
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. 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.
@tagdp
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 twodimensional 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][k1] , 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
Java

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]; } } }

// OJ: https://leetcode.com/problems/guessnumberhigherorlowerii/ // 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(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]