> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Guess Number Higher or Lower II

> Tested Python solution for LeetCode 375 with 28 pytest cases. Generate a practice environment with lcpy.

LeetCode 375, [Medium](/catalog/medium). Topics: [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), Minimax, [Game Theory](/catalog/topics/game-theory). [View on LeetCode](https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/).

Generate this problem as a practice environment: tested reference solution, 28 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 375   # by problem number
lcpy gen -s guess_number_higher_or_lower_ii   # by problem name
```

## Problem

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

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

Given a particular \<code>n\</code>, return \<em>the minimum amount of money you need to \<strong>guarantee a win regardless of what number I pick\</strong>\</em>.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/09/10/graph.png)

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

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

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/guess_number_higher_or_lower_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/guess_number_higher_or_lower_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^3)
    # Space: O(n^2)
    def get_money_amount(self, n: int) -> int:
        # dp[lo][hi] = min worst-case cost to guarantee a win within [lo, hi].
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for length in range(2, n + 1):
            for lo in range(1, n - length + 2):
                hi = lo + length - 1
                dp[lo][hi] = min(x + max(dp[lo][x - 1], dp[x + 1][hi]) for x in range(lo, hi))
        return dp[1][n]
```

## Complexity

| Time | Space |
| - | - |
| O(n^3) | O(n^2) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.