# 375     Guess Number Higher or Lower II

## 375. [Guess Number Higher or Lower II](https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/)

## 1. Question

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

## 2. Implementation

**(1) Memoization**

```java
class Solution {
    public int getMoneyAmount(int n) {
        int[][] cache = new int[n + 1][n + 1];
        return getMoneyByDFS(1, n, cache);
    }

    public int getMoneyByDFS(int start, int end, int[][] cache) {
        if (start >= end) {
            return 0;
        }

        if (cache[start][end] != 0) {
            return cache[start][end];
        }

        int cost = Integer.MAX_VALUE;
        int mid = start + (end - start) / 2;
        for (; mid <= end; mid++) {
            cost = Math.min(cost, mid + Math.max(getMoneyByDFS(start, mid - 1, cache), getMoneyByDFS(mid + 1, end, cache)));
        }

        cache[start][end] = cost;
        return cost;
    }
}
```

**(2) DP**

```java
class Solution {
    public int getMoneyAmount(int n) {
        // 因为数字从1开始，为了方便计算将dp维度变成 n + 1
        // dp[i][j]代表在[i...j]这个区间里猜数字, 为了保证能赢而需要支付的最少花费
        int[][] dp = new int[n + 1][n + 1];

        for (int len = 1; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                // 当start等于end时，说明猜中数，不需要任何花费
                if (start == end) {
                    continue;
                }

                dp[start][end] = Integer.MAX_VALUE;

                for (int mid = start; mid < end; mid++) {
                    // 因为是要求的是保证能赢的情况，所以我们总是要考虑最坏的情况，所以我们[start, end]的区间枚举出可能猜中的数时，
                    // 在[start, mid - 1],[mid + 1, end]两个区间中，我们取得到花费较高的区间
                    dp[start][end] = Math.min(dp[start][end], mid + Math.max(dp[start][mid - 1], dp[mid  + 1][end]));
                }
            }
        }
        return dp[1][n];
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n ^ 3), 空间复杂度O(n ^ 2)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/interval-dp/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.