Comment on page

# 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.

## 代码

### Approach #1 Recursion [Time Lmit Exceeded]

Time: O(N!) && Space: O(N)
class Solution {
public int getMoneyAmount(int n) {
return calculate(1, n);
}
private int claculate(int low, int high) {
if (low >= high) return 0;
int minres = Integer.MAX_VALUE;
int mid = (low + high) / 2;
for (int i = mid; i <= high; i++) {
int res = i + Math.max(calculate(i+1, high), calculate(low, i - 1));
minres = Math.min(res, minres);
}
return minres;
}
}

### Approach #2 Recursion with memo

class Solution {
public int getMoneyAmount(int n) {
int[][] memo = new int[n+1][n+1];
return calculate(memo, 1, n);
}
private int calculate(int[][] memo, int start, int end) {
if (start >= end) return 0;
if (memo[start][end] != 0) return memo[start][end];
int res = Integer.MAX_VALUE;
int mid = (start + end) / 2; // from i = start to end
for (int i = mid; i <= end; i++) {
int localMax = i + Math.max(calculate(memo, start, i - 1), calculate(memo, i+1, end));
res = Math.min(res, localMax);
}
memo[start][end] = res;
return res;
}
}

### Approach #3 DP Bottom Up

Time `O(n^3)` Space `O(N^2)`
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int start = 1; start + len - 1 <= n; start++) {
int end = start + len - 1;
int minres = Integer.MAX_VALUE;
for (int piv = start; piv < end; piv++) {
int res = piv + Math.max(dp[start][piv-1], dp[piv+1][end]);
minres = Math.min(res, minres);
}
dp[start][end] = minres;
}
}
return dp[1][n];
}
}

### Approach #4 Better Approach Using DP

public class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int start = 1; start + len - 1 <= n; start++) {
int end = start + len - 1;
int mid = start + (len - 1) / 2;
int minres = Integer.MAX_VALUE;
for (int piv = mid; piv < end; piv++) {
int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][end]);
minres = Math.min(res, minres);
}
dp[start][end] = minres;
}
}
return dp[1][n];
}
}