Guess Number Higher or Lower II

Problem Statement

In the Guessing Game, a scenario is set up where one player selects a number between 1 and a given n, and another player is tasked with guessing that number. Each guess comes with a monetary penalty equivalent to the wrongly guessed number if it is incorrect. The key strategic challenge in this game is to optimize the guesses such that the penalty incurred, in the worst case, is minimized. The question then becomes: what is the minimum amount of money required to guarantee a win regardless of the number selected by the first player?

Examples

Example 1

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

Approach and Intuition

The solution to this game revolves around a strategic application of binary search and dynamic programming. The goal is to minimize the worst-case monetary loss through optimal guessing. Here’s how one should think about the problem:

1. Binary Search Application:

   • Given a number range, the typical strategy is to guess somewhere in the middle initially.
   • Depending on whether the actual number is higher or lower than the guess, the possible range of numbers narrows down, allowing for a refined subsequent guess.

2. Dynamic Programming (Minimax Strategy):

   • For a given range [i, j], the strategy involves choosing a guess that minimizes the maximum loss (hence the use of the term 'minimax').
   • The cost of a guess includes the guess itself plus the maximum of two scenarios: the cost of guessing too low, or the cost of guessing too high.
   • Recursively apply this strategy to all possible ranges and guesses.

3. Decision Making for Worst-case Scenario:

   • For every possible initial guess, calculate the cost considering that subsequent guesses might be either too high or too low, and one must bear the cost accordingly.
   • The choice of the initial guess is critical: it's not always optimal to guess in the exact middle of a range because the cost calculated is not symmetrically distributed—it depends on the range and the specific dynamics of the costs as they accumulate.

4. Computational Complexity Management:

   • Given that n can be as large as 200, an efficient solution must manage the computational complexity, ideally aiming for a complexity no worse than polynomial time.
   • Use memoization or bottom-up dynamic programming to store the results of subproblems, thus avoiding redundant calculations and reducing time complexity.

To better grasp this, let us reference the example where n = 10. The strategic guessing involves starting from 7, then adjusting the guesses based on whether the actual number is higher or lower. The total costs are calculated by considering the worst sequence of wrong guesses leading up to the right guess. By analyzing the problem with dynamic programming, we iteratively determine the minimum amount needed to guarantee a win, which can be computed to be $16 in the worst case for n = 10.

Solutions

public class Solution {
    public int calculateMinimum(int max) {
        int[][] table = new int[max + 1][max + 1];

        for (int length = 2; length <= max; length++) {
            for (int begin = 1; begin <= max - length + 1; begin++) {
                int lowest = Integer.MAX_VALUE;
                for (int pivot = begin + (length - 1) / 2; pivot < begin + length - 1; pivot++) {
                    int cost = pivot + Math.max(table[begin][pivot - 1], table[pivot + 1][begin + length - 1]);
                    lowest = Math.min(cost, lowest);
                }
                table[begin][begin + length - 1] = lowest;
            }
        }
        return table[1][max];
    }
}