LeetCode 375: Guess Number Higher or Lower II

Problem Restatement

We are playing a guessing game.

A number is picked from:

1 to n

Each time we guess a number x:

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:

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

Example function shape:

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

Examples

Example 1:

n = 1

There is only one possible number.

We guess 1 and win immediately.

Cost:

0

So the answer is:

0

Example 2:

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:

1

So the answer is:

1

Example 3:

n = 10

The answer is:

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:

dp[left][right]

mean:

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:

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:

[left, x - 1]

or:

[x + 1, right]

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

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:

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:

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:

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:

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.

With n <= 200, this is acceptable.

Implementation

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:

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

This makes expressions like:

dp[guess + 1][right]

safe even when guess == right.

We process by interval length:

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

Length 1 intervals already have cost 0.

For each interval:

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

we try every possible first guess:

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

The cost of choosing that guess is:

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:

dp[left][right] = best

stores the optimal guaranteed cost for this interval.

Testing

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: