Guess Number Higher or Lower II

medium dp interval dp minimax

Problem

Pick a number in [1, n]. On each wrong guess g you pay $g; the game tells you only "higher" or "lower". Return the minimum cash you must guarantee a win.

Inputn = 10

Output16

dp[l][r] = min over k in [l,r] of (k + max(dp[l][k−1], dp[k+1][r])).

n (1..10)

def get_money_amount(n):
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(2, n + 1):
        for l in range(1, n - length + 2):
            r = l + length - 1
            dp[l][r] = float("inf")
            for k in range(l, r + 1):
                left = dp[l][k - 1] if k > l else 0
                right = dp[k + 1][r] if k < r else 0
                dp[l][r] = min(dp[l][r], k + max(left, right))
    return dp[1][n]

function getMoneyAmount(n) {
  const dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
  for (let length = 2; length <= n; length++) {
    for (let l = 1; l + length - 1 <= n; l++) {
      const r = l + length - 1;
      dp[l][r] = Infinity;
      for (let k = l; k <= r; k++) {
        const left = k > l ? dp[l][k - 1] : 0;
        const right = k < r ? dp[k + 1][r] : 0;
        dp[l][r] = Math.min(dp[l][r], k + Math.max(left, right));
      }
    }
  }
  return dp[1][n];
}

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 2][n + 2];
        for (int length = 2; length <= n; length++) {
            for (int l = 1; l + length - 1 <= n; l++) {
                int r = l + length - 1;
                dp[l][r] = Integer.MAX_VALUE;
                for (int k = l; k <= r; k++) {
                    int left = k > l ? dp[l][k - 1] : 0;
                    int right = k < r ? dp[k + 1][r] : 0;
                    dp[l][r] = Math.min(dp[l][r], k + Math.max(left, right));
                }
            }
        }
        return dp[1][n];
    }
}

int getMoneyAmount(int n) {
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int length = 2; length <= n; length++) {
        for (int l = 1; l + length - 1 <= n; l++) {
            int r = l + length - 1;
            dp[l][r] = INT_MAX;
            for (int k = l; k <= r; k++) {
                int left = k > l ? dp[l][k - 1] : 0;
                int right = k < r ? dp[k + 1][r] : 0;
                dp[l][r] = min(dp[l][r], k + max(left, right));
            }
        }
    }
    return dp[1][n];
}

Explanation

You must guarantee a win, so you have to plan for the worst case: even if the hidden number is the most expensive one to find, you should still have enough cash. This is a minimax problem solved with interval DP.

Define dp[l][r] = the minimum cash you must guarantee to win when the answer is somewhere in the range [l, r]. A range with a single number costs 0 because you just guess it.

For a bigger range, you pick some guess k. If it's wrong you pay k, and the answer is now in either [l, k-1] or [k+1, r]. Since the worst case decides, you take the max of those two sub-costs. The cost of choosing k is k + max(dp[l][k-1], dp[k+1][r]), and you keep the min over all k.

We fill the table by increasing range length so every smaller subrange is already solved when we need it. The final answer is dp[1][n].

Example: for n = 10 the careful min-over-max bookkeeping gives 16 — that's the smallest budget that always wins, no matter the hidden number.

Time: O(n³) Space: O(n²)