# Guess Number Higher or Lower II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/guess-number-higher-or-lower-ii)
Canonical: https://scaleengineer.com/dsa/problems/guess-number-higher-or-lower-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
---
## Problem
We are playing the Guessing Game. The game will work as follows:

1. I pick a number between `1` and `n`.
2. You guess a number.
3. If you guess the right number, **you win the game**.
4. If you guess the wrong number, then I will tell you whether the number I picked is **higher or lower**, and you will continue guessing.
5. Every time you guess a wrong number `x`, you will pay `x` dollars. If you run out of money, **you lose the game**.

Given a particular `n`, return _the minimum amount of money you need to **guarantee a win regardless of what number I pick**_.

**Example 1:**

![](https://assets.glich.co/dsa/guess-number-higher-or-lower-ii/image0.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.

**Example 2:**

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

**Example 3:**

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

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's logic into a recursive function. For any given range of numbers `[start, end]`, we explore every possible number `x` as our first guess. The cost associated with guessing `x` is `x` plus the cost of the subsequent worst-case scenario. The worst-case scenario is the one that costs more: either guessing in the lower sub-range `[start, x-1]` or the higher sub-range `[x+1, end]`. We then choose the guess `x` that minimizes this total worst-case cost. This method explores the entire tree of possibilities without any optimization.
**Time:** Exponential, roughly O(n!). The function branches for each element in the range, and subproblems are recomputed many times. This is too slow for the given constraints. · **Space:** O(n), for the recursion stack depth. In the worst case, the recursion can go `n` levels deep.
**Pros:** Simple to understand and implement as it directly models the problem's recursive nature.; Provides a clear, albeit inefficient, baseline for solving the problem.
**Cons:** Extremely inefficient due to a massive number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for even small values of `n` (e.g., n > 10).
### Explanation
The problem asks for a strategy that minimizes the maximum possible cost, which is a classic minimax problem. We can define a function `solve(start, end)` that calculates the minimum cost to guarantee a win for a given range of numbers `[start, end]`. To compute this, we try every number `x` in the range as our first guess. If we guess `x`, we pay `x` dollars. The opponent then tells us if their number is higher or lower. To guarantee a win, we must prepare for the worst possible outcome. The cost for guessing `x` is `x` plus the cost of the harder of the two resulting subproblems: `[start, x-1]` or `[x+1, end]`. Therefore, the cost for a given guess `x` is `x + max(solve(start, x-1), solve(x+1, end))`. Our goal is to choose the guess `x` that minimizes this cost. This gives us the recurrence relation: `solve(start, end) = min_{x=start..end} { x + max(solve(start, x-1), solve(x+1, end)) }`. The base case for the recursion is when `start >= end`, which means there's at most one number left. We can guess it with no cost, so `solve(start, end) = 0`. This logic is implemented as a straightforward recursive function.

```java
public class Solution {
    public int getMoneyAmount(int n) {
        return solve(1, n);
    }

    private int solve(int start, int end) {
        if (start >= end) {
            return 0;
        }
        int minCost = Integer.MAX_VALUE;
        for (int x = start; x <= end; x++) {
            int cost = x + Math.max(solve(start, x - 1), solve(x + 1, end));
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }
}
```
### Algorithm
1. Define a recursive function `solve(start, end)` that returns the minimum cost to guarantee a win for the range `[start, end]`.
2. **Base Case:** If `start >= end`, it means there is at most one number in the range. We can guess it correctly on the first try, so the cost is 0. Return 0.
3. Initialize a variable `minCost` to a very large value (e.g., `Integer.MAX_VALUE`).
4. Iterate through all possible first guesses `x` from `start` to `end`.
5. For each guess `x`, calculate the cost if we choose `x`. This cost is `x` (for the current guess) plus the maximum cost of the subsequent subproblems, which is `max(solve(start, x - 1), solve(x + 1, end))`.
6. Update `minCost` with the minimum cost found so far: `minCost = min(minCost, currentCost)`.
7. After checking all possible guesses `x`, return `minCost`.
8. The initial call to find the solution for the range `[1, n]` is `solve(1, n)`.

## Top-Down Dynamic Programming (Memoization)
This approach enhances the brute-force recursion by using memoization to eliminate redundant calculations. The core recursive logic remains the same, but we introduce a cache (typically a 2D array) to store the results of subproblems that have already been solved. Before computing the minimum cost for a range `[start, end]`, we first check our cache. If the result is present, we use it directly. If not, we compute it, store it in the cache for future use, and then return it. This technique, also known as top-down dynamic programming, ensures that each unique subproblem is solved only once, dramatically improving the efficiency.
**Time:** O(n^3). There are O(n^2) possible subproblems (ranges `[i, j]`). For each subproblem, we iterate up to `n` times to find the optimal guess `x`. Thus, the total complexity is O(n^2 * n) = O(n^3). · **Space:** O(n^2), primarily for the memoization table. The recursion stack depth adds an O(n) factor, but it's dominated by the table.
**Pros:** Significantly more efficient than brute-force recursion, making it feasible for the given constraints.; Maintains the logical structure of the recursive solution, which can be easier to reason about.; Guarantees finding the optimal solution.
**Cons:** Requires O(n^2) space for the memoization table, which can be significant for very large `n`.; The recursive calls still have some overhead compared to a purely iterative solution.
### Explanation
The plain recursive solution is slow because it repeatedly solves the same subproblems. For instance, `solve(3, 5)` might be needed when calculating `solve(1, 10)` (e.g., if we guess 2) and also when calculating `solve(1, 8)` (e.g., if we guess 2). To fix this, we can use a 2D array, `memo[n+1][n+1]`, to store the results. `memo[i][j]` will hold the computed minimum cost for the range `[i, j]`. The recursive function `solve(start, end)` is modified to first check if `memo[start][end]` contains a pre-computed answer. If it does, the stored value is returned. Otherwise, the function proceeds with the calculation as in the brute-force approach. Once the result is found, it's stored in `memo[start][end]` before being returned. This ensures that the expensive computation for each subproblem `(start, end)` is performed only once.

```java
public class Solution {
    private int[][] memo;

    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return solve(1, n);
    }

    private int solve(int start, int end) {
        if (start >= end) {
            return 0;
        }
        if (memo[start][end] != 0) {
            return memo[start][end];
        }

        int minCost = Integer.MAX_VALUE;
        // To reduce the search space, we can observe that the optimal first guess `x`
        // will likely be in the upper half of the range to balance the cost `x`
        // against the cost of the subproblems. We can start searching from the middle.
        for (int x = (start + end) / 2; x <= end; x++) {
            int cost = x + Math.max(solve(start, x - 1), solve(x + 1, end));
            minCost = Math.min(minCost, cost);
        }
        
        memo[start][end] = minCost;
        return minCost;
    }
}
```
### Algorithm
1. Create a 2D array `memo` of size `(n+1) x (n+1)` to store the results of subproblems. Initialize it with a value (e.g., 0 or -1) to indicate that a subproblem has not been solved.
2. Define a recursive helper function `solve(start, end)`.
3. **Base Case:** If `start >= end`, return 0.
4. **Memoization Check:** If `memo[start][end]` has already been computed (i.e., not the initial value), return it directly.
5. If not computed, initialize `minCost` to `Integer.MAX_VALUE`.
6. Iterate through all possible guesses `x` from `start` to `end`.
7. For each `x`, recursively calculate the cost: `cost = x + max(solve(start, x - 1), solve(x + 1, end))`.
8. Update `minCost = min(minCost, cost)`.
9. **Store Result:** Before returning, store the computed minimum cost in the memoization table: `memo[start][end] = minCost`.
10. Return `minCost`.
11. The initial call is `solve(1, n)`.

## Bottom-Up Dynamic Programming (Tabulation)
This approach solves the problem iteratively using bottom-up dynamic programming, also known as tabulation. It avoids recursion and its associated overhead, often leading to better performance. We use a 2D table, `dp[i][j]`, to store the minimum cost to guarantee a win for the number range `[i, j]`. The key idea is to fill this table by starting with the smallest subproblems (ranges of length 2) and progressively building up to the solution for the full range `[1, n]`. By iterating through range lengths, we ensure that when we calculate `dp[i][j]`, the solutions for all smaller, required subproblems (like `dp[i][k-1]` and `dp[k+1][j]`) have already been computed and stored in the table.
**Time:** O(n^3). The three nested loops for `len`, `i`, and `k` dominate the runtime. `len` runs up to `n`, `i` runs up to `n`, and `k` runs up to `n` times in the worst case. · **Space:** O(n^2), for the 2D DP table.
**Pros:** Generally the most efficient solution for the given constraints due to the absence of recursion overhead.; Iterative nature can make it easier to analyze and debug.; Guarantees the optimal solution.
**Cons:** Can be slightly less intuitive to formulate than the recursive top-down approach.; Still has a cubic time complexity, which might be too slow for much larger constraints.
### Explanation
Instead of starting from the top problem `(1, n)` and breaking it down, the bottom-up approach starts with the smallest problems and builds up. We use a 2D array `dp[n+2][n+2]` where `dp[i][j]` stores the solution for the subproblem on the range `[i, j]`. The base cases are ranges of length 0 or 1, for which the cost is 0. Our DP table is initialized to 0, which covers these cases. We then iterate on the length of the range, `len`, from 2 to `n`. For each `len`, we iterate through all possible start indices `i`. The end index `j` is simply `i + len - 1`. For each range `[i, j]`, we calculate `dp[i][j]` by trying every possible split point `k` (our first guess) from `i` to `j`. The cost for guessing `k` is `k + max(dp[i][k-1], dp[k+1][j])`. Since we are iterating by increasing length, the values `dp[i][k-1]` (for range length `k-i`) and `dp[k+1][j]` (for range length `j-k`) are guaranteed to have been computed in previous iterations. We take the minimum cost over all possible `k`. The final answer is the value stored in `dp[1][n]`.

```java
public class Solution {
    public int getMoneyAmount(int n) {
        if (n == 1) {
            return 0;
        }
        // dp[i][j] = min cost for range [i, j]
        int[][] dp = new int[n + 2][n + 2];

        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    int cost = k + Math.max(dp[i][k - 1], dp[k + 1][j]);
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[1][n];
    }
}
```
### Algorithm
1. Create a 2D DP table `dp` of size `(n+2) x (n+2)` and initialize all its values to 0. The extra padding helps handle boundary cases like `k-1` and `k+1` without extra checks.
2. Iterate over the length of the range, `len`, from 2 to `n`.
3. Inside this loop, iterate over all possible starting points `i` for a range of length `len`. The loop for `i` will go from 1 up to `n - len + 1`.
4. Calculate the end point of the current range: `j = i + len - 1`.
5. For the current range `[i, j]`, initialize its cost `dp[i][j]` to `Integer.MAX_VALUE`.
6. Iterate through all possible first guesses `k` from `i` to `j`.
7. For each guess `k`, calculate the cost using the already computed values from smaller sub-ranges: `cost = k + max(dp[i][k-1], dp[k+1][j])`.
8. Update the minimum cost for the range `[i, j]`: `dp[i][j] = min(dp[i][j], cost)`.
9. After all loops complete, the value `dp[1][n]` will contain the minimum cost to guarantee a win for the entire range `[1, n]`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int getMoneyAmount(int n) {
    int[][] dp = new int[n + 10][n + 10];
    for (int l = 2; l <= n; ++l) {
      for (int i = 1; i + l - 1 <= n; ++i) {
        int j = i + l - 1;
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i; k <= j; ++k) {
          int t = Math.max(dp[i][k - 1], dp[k + 1][j]) + k;
          dp[i][j] = Math.min(dp[i][j], t);
        }
      }
    }
    return dp[1][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getMoneyAmount(int n) {
    vector<vector<int>> dp(n + 10, vector<int>(n + 10));
    for (int l = 2; l <= n; ++l) {
      for (int i = 1; i + l - 1 <= n; ++i) {
        int j = i + l - 1;
        dp[i][j] = INT_MAX;
        for (int k = i; k <= j; ++k) {
          int t = max(dp[i][k - 1], dp[k + 1][j]) + k;
          dp[i][j] = min(dp[i][j], t);
        }
      }
    }
    return dp[1][n];
  }
};

```

### Python

```python
class Solution : def getMoneyAmount ( self , n : int ) -> int : dp = [[ 0 ] * ( n + 10 ) for _ in range ( n + 10 )] for l in range ( 2 , n + 1 ): for i in range ( 1 , n - l + 2 ): j = i + l - 1 dp [ i ][ j ] = inf for k in range ( i , j + 1 ): t = max ( dp [ i ][ k - 1 ], dp [ k + 1 ][ j ]) + k dp [ i ][ j ] = min ( dp [ i ][ j ], t ) return dp [ 1 ][ n ]
```