# 375.Guess-Number-Higher-or-Lower-II

## 375. Guess Number Higher or Lower II

## 题目地址

<https://leetcode.com/problems/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)

```java
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

```java
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)`

```java
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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/qu-jian-xing/375.guess-number-higher-or-lower-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.