Guess Number Higher or Lower II

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.

For example: 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.

def getMoneyAmount(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    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 pivot in range(start, end):
                cost = pivot + max(dp[start][pivot - 1], dp[pivot + 1][end])
                dp[start][end] = min(dp[start][end], cost)

    return dp[1][n]

# Example usage:
n = 10
result = getMoneyAmount(n)
print(f"Minimum amount needed for n = {n}: {result}") # Output: 16

n = 1
result = getMoneyAmount(n)
print(f"Minimum amount needed for n = {n}: {result}") # Output: 0

n = 2
result = getMoneyAmount(n)
print(f"Minimum amount needed for n = {n}: {result}") # Output: 1

Explanation:

This problem can be solved using dynamic programming. The core idea is to consider every number i in the range [1, n] as a potential guess. For each guess, we need to consider the worst-case scenario, i.e., whether the number is lower or higher than our guess.

1. Naive Approach (Brute Force - Not practical):

   • Try every possible guess in the range [1, n]. For each guess, recursively calculate the cost for the lower and higher ranges. Choose the guess that minimizes the maximum cost of the two ranges.
   • This approach leads to exponential time complexity, making it impractical for larger values of n.

2. Optimal Solution (Dynamic Programming):

   • Create a 2D DP table where dp[i][j] represents the minimum amount of money needed to guarantee a win within the range [i, j].
   • The base case is when i >= j, where dp[i][j] = 0 because no guess is needed.
   • For each range [i, j], iterate through every possible guess pivot from i to j.
   • Calculate the cost of guessing pivot as pivot + max(dp[i][pivot-1], dp[pivot+1][j]). The max function is used because we want to consider the worst-case scenario whether the number is lower or higher than pivot.
   • The value of dp[i][j] will be the minimum cost among all possible pivot values.

Big(O) Run-time Analysis:

The dynamic programming solution has a time complexity of O(n^3). This is because we have a nested loop to fill the DP table. The outer loops iterate through all possible lengths and start positions, which take O(n^2) time. The inner loop iterates through all possible pivot values within each range, which takes O(n) time. Therefore, the total time complexity is O(n^2 * n) = O(n^3).

Big(O) Space Usage Analysis:

The space complexity of the dynamic programming solution is O(n^2) because we use a 2D DP table of size (n+1) x (n+1) to store the minimum costs for all possible ranges. This table is necessary to memoize the results of subproblems and avoid redundant calculations.

Edge Cases:

1. n = 1: The minimum amount of money needed is 0 because there is only one possible number, so you can guess it directly.
2. n = 2: The minimum amount of money needed is 1. You can guess 1. If it's the correct number, the cost is 0. If not, the number must be 2, so you guess 2 and pay 1.
3. n = Larger value (e.g., 200): The dynamic programming approach efficiently handles larger values of n by breaking the problem into smaller subproblems and storing the results in the DP table.

Handling the edge cases and using dynamic programming ensures that the solution is both correct and efficient for all possible values of n within the given constraints.