Guess Number Higher or Lower II (LeetCode 375): Minimax DP

LeetCode 375: Guess Number Higher or Lower II looks like a natural sequel to Guess Number Higher or Lower, but the goal has shifted in an important way. In problem 374 you are minimizing the number of guesses needed in the worst case. Here you are minimizing the total money you spend if you keep guessing wrong. Paying k to guess k and be told you are wrong makes the cost of a bad guess proportional to its value. That asymmetry changes everything.

The problem

You pick a number in the range [1, n]. I have a secret number. Whenever you guess k and the answer is not k, you pay k dollars. If you guess right, you pay nothing. You want a strategy that guarantees you can find the secret number while spending as little money as possible in the worst case. Return that minimum guaranteed amount.

For example, with n = 10, one strategy is to always guess the midpoint. If you guess 7 and the answer is lower, you have paid 7 and now need to search [1, 6]. If the answer is higher, you search [8, 10]. You take the more expensive branch (the worst case) and add 7 to that cost. You want to choose your pivot so that the maximum of the two sub-costs is as small as possible.

Why minimax?

At every step you are making a decision (which number to guess) and an adversary is picking the worst possible outcome (whether the answer is in the left or right half after your guess). This is the classic setup for minimax: minimize over your choices, maximize over the adversary's responses.

That two-level optimization is what drives the recurrence:

dp[i][j] = min over k in [i, j] of:
               k + max(dp[i][k-1], dp[k+1][j])

You pick pivot k. You pay k. The adversary tells you whether the answer is in [i, k-1] or [k+1, j], and they pick whichever costs you more. You choose the k that keeps that worst case as low as possible.

The base cases: dp[i][i] = 0. If there is only one number in the range, you already know it. No guessing needed, no money spent. By convention, dp[i][k-1] when k == i (empty left sub-range) evaluates to 0, and dp[k+1][j] when k == j (empty right sub-range) also evaluates to 0.

Building the DP table bottom-up

Interval DP always fills by increasing length. You cannot compute dp[1][5] until you know dp[1][2], dp[3][5], and other smaller intervals. So you iterate over all lengths from 2 up to n, and for each length you iterate over all starting positions.

def getMoneyAmount(n):
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(2, n + 1):
        for start in range(1, n - length + 2):
            end = start + length - 1
            dp[start][end] = float('inf')
            for k in range(start, end + 1):
                cost = k + max(dp[start][k - 1], dp[k + 1][end])
                dp[start][end] = min(dp[start][end], cost)
    return dp[1][n]

The table is sized (n + 2) x (n + 2) to avoid out-of-bounds access when k == start (accessing dp[start][k-1] = dp[start][start-1]) or k == end (accessing dp[k+1][end] = dp[end+1][end]). Both of these are zero in a zero-initialized table, which is exactly what we want for empty ranges.

Complexity

Three nested loops: length, start, and pivot k. The table has O(n^2) cells. For the constraints LeetCode gives (n up to 200), this runs comfortably within limits.

Building blocks

This problem sits at the intersection of two important patterns.

Interval DP is the pattern where the state is a contiguous subrange [i, j] and you fill the table by increasing interval length. You have seen it in problems like Burst Balloons, where you pick which balloon to burst last inside an interval. The key insight in every interval DP problem is the same: the order you solve subproblems must respect the dependency structure, and filling by length guarantees that.

Minimax is the decision framework where you alternate between minimizing (your choice of pivot) and maximizing (the adversary's choice of which branch to send you down). It shows up across game theory, search algorithms, and adversarial optimization. Recognizing the pattern here as minimax rather than just "find the minimum" is the conceptual leap.

When you see an interval DP where the transition involves taking the maximum of two sub-costs, minimax is almost always the right frame.

Edge cases

• n = 1: the range [1, 1] has one number. You already know it. The answer is 0. The loop for length starting at 2 never executes, so dp[1][1] = 0 is returned directly.
• Picking the midpoint is optimal in balanced cases: when a range has roughly equal sub-ranges on both sides of a pivot, the worst case is minimized. For [1, 5], picking k = 3 gives 3 + max(dp[1][2], dp[4][5]) = 3 + max(1, 4) = 7. Picking k = 2 gives 2 + max(0, dp[3][5]) = 2 + 4 = 6. The midpoint intuition holds for large n but the exact optimal pivot can shift for small ranges, which is why you try every k rather than hardcoding the middle.
• Empty sub-ranges: when k == start, dp[start][k-1] = dp[start][start-1]. Since start-1 < start, this cell is never written to and stays 0. Same logic for the right boundary. The zero-initialized table handles this automatically.

From understanding to recall

You can trace through this post and follow every step. The harder question: can you reconstruct the recurrence in an interview without notes? Can you remember that you fill by length, not by start index? Can you recall why the table needs n + 2 columns?

These details are easy to lose. Spaced repetition solves that by having you write out the recurrence and the loop structure at increasing intervals. After a few reps, the pattern becomes automatic. You are not memorizing code, you are internalizing the reasoning, so you can reconstruct it from first principles even under pressure.

The minimax DP pattern is one of a manageable set of building blocks that covers a large fraction of medium and hard LeetCode problems. Drilling each block individually is more efficient than trying to grind through problems randomly and hoping patterns emerge on their own.

Related posts

• Guess Number Higher or Lower - The binary search version of this problem, where you minimize the number of guesses rather than the total cost
• Coin Change - Classic DP where you minimize a total cost across choices, using a simpler linear state rather than an interval
• Burst Balloons - Another interval DP problem where you pick what happens last inside a range, and the same fill-by-length technique applies