# LeetCode 375: Guess Number Higher or Lower II

## Problem Restatement

We are playing a guessing game.

A number is picked from:

```python
1 to n
```

Each time we guess a number `x`:

| Result | Cost |
|---|---:|
| Guess is correct | Pay `0` |
| Guess is wrong | Pay `x` dollars |

If the guess is wrong, we are told whether the hidden number is higher or lower, then we continue guessing in the remaining range.

We need to return the minimum amount of money required to guarantee a win no matter which number was picked.

The constraint is:

```python
1 <= n <= 200
```

The official examples include `n = 1`, answer `0`, and `n = 2`, answer `1`. The classic larger example is `n = 10`, answer `16`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Minimum money needed to guarantee a win |
| Range | Hidden number is between `1` and `n` |
| Wrong guess cost | Pay the guessed number |
| Correct guess cost | Pay nothing |

Example function shape:

```python
def getMoneyAmount(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 1
```

There is only one possible number.

We guess `1` and win immediately.

Cost:

```python
0
```

So the answer is:

```python
0
```

Example 2:

```python
n = 2
```

There are two possible numbers: `1` and `2`.

Guess `1`.

If it is correct, pay `0`.

If it is wrong, pay `1`, and the number must be `2`.

Worst-case cost:

```python
1
```

So the answer is:

```python
1
```

Example 3:

```python
n = 10
```

The answer is:

```python
16
```

One optimal strategy starts by guessing `7`.

If the number is higher, the remaining range is `[8, 10]`.

If the number is lower, the remaining range is `[1, 6]`.

The strategy is chosen to minimize the worst-case total cost.

## First Thought: Binary Search

For the normal Guess Number problem, binary search is natural.

But here the cost is the guessed number.

Binary search minimizes the number of guesses, not the amount of money paid.

For example, guessing a larger number early may cost more if it is wrong.

So we need to optimize for worst-case money, not guess count.

This makes it an interval dynamic programming problem.

## Key Insight

Let:

```python
dp[left][right]
```

mean:

```text
minimum money needed to guarantee a win if the hidden number is in [left, right]
```

If `left >= right`, there is at most one number, so no money is needed:

```python
dp[left][right] = 0
```

Now suppose we guess `x` first inside `[left, right]`.

If `x` is correct, cost is `0`.

If `x` is wrong, we pay `x`.

Then the hidden number is either:

```text
[left, x - 1]
```

or:

```text
[x + 1, right]
```

Since we need to guarantee a win, we must handle the more expensive side:

```python
x + max(dp[left][x - 1], dp[x + 1][right])
```

We can choose the first guess `x`, so we take the minimum over all possible guesses:

```python
dp[left][right] =
min over x in [left, right] of x + max(dp[left][x - 1], dp[x + 1][right])
```

## Algorithm

Use bottom-up interval DP.

1. Create a table:

```python
dp = [[0] * (n + 2) for _ in range(n + 2)]
```

2. Process interval lengths from `2` to `n`.

3. For each interval `[left, right]`:
   - Try every first guess `x`.
   - Compute the worst-case cost.
   - Store the minimum cost.

4. Return:

```python
dp[1][n]
```

## Correctness

For an interval with one number, the cost is `0` because we can guess that number and pay nothing.

For a larger interval `[left, right]`, the first guess must be some number `x` inside the interval.

If `x` is wrong, the game moves to either the left interval or the right interval. Since we need enough money to win regardless of the picked number, the cost of choosing `x` must include the more expensive of those two subproblems.

So the guaranteed cost for first guess `x` is:

```python
x + max(dp[left][x - 1], dp[x + 1][right])
```

The algorithm tries every possible first guess and chooses the one with the smallest guaranteed cost.

Because the DP fills smaller intervals before larger intervals, every subproblem used in the transition has already been computed.

Therefore, `dp[left][right]` is correct for every interval, and `dp[1][n]` is the minimum money needed to guarantee a win for the full game.

## Complexity

Let `n` be the input value.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` | There are `O(n^2)` intervals, and each tries `O(n)` guesses |
| Space | `O(n^2)` | DP table over all intervals |

With `n <= 200`, this is acceptable.

## Implementation

```python
class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        for length in range(2, n + 1):
            for left in range(1, n - length + 2):
                right = left + length - 1
                best = float("inf")

                for guess in range(left, right + 1):
                    cost = guess + max(
                        dp[left][guess - 1],
                        dp[guess + 1][right],
                    )
                    best = min(best, cost)

                dp[left][right] = best

        return dp[1][n]
```

## Code Explanation

The DP table has extra padding:

```python
dp = [[0] * (n + 2) for _ in range(n + 2)]
```

This makes expressions like:

```python
dp[guess + 1][right]
```

safe even when `guess == right`.

We process by interval length:

```python
for length in range(2, n + 1):
```

Length `1` intervals already have cost `0`.

For each interval:

```python
left = ...
right = left + length - 1
```

we try every possible first guess:

```python
for guess in range(left, right + 1):
```

The cost of choosing that guess is:

```python
guess + max(
    dp[left][guess - 1],
    dp[guess + 1][right],
)
```

We pay `guess` only when the guess is wrong. The worst case always assumes the hidden number is on the more expensive side.

Finally:

```python
dp[left][right] = best
```

stores the optimal guaranteed cost for this interval.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.getMoneyAmount(1) == 0
    assert s.getMoneyAmount(2) == 1
    assert s.getMoneyAmount(3) == 2
    assert s.getMoneyAmount(4) == 4
    assert s.getMoneyAmount(10) == 16

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Single number costs nothing |
| `n = 2` | Smallest non-trivial interval |
| `n = 3` | Best first guess is the middle |
| `n = 4` | Checks interval recurrence |
| `n = 10` | Standard larger example |