Guess Number Higher or Lower II

The problem is the Guessing Game, where you must find the minimum amount of money needed to guarantee a win, given that the number to guess is between 1 and ( n ). To find the solution, we will employ a dynamic programming approach.

Key Insight

The strategy here is to find the guess that minimizes the maximum loss. For every possible number ( x ) to guess, you need to calculate the cost considering that the actual number is either higher or lower than ( x ), and then find the maximum between these two costs.

Algorithm

  1. Initialize a Table: Create a 2D table ( dp ) of size ( (n + 1) \times (n + 1) ) to store the results for each subproblem. ( dp[i][j] ) will represent the minimum cost needed to guess the number between ( i ) and ( j ).
  2. Bottom-Up Approach: Use a bottom-up approach to fill the table, starting from smaller ranges and building up to the range ( [1, n] ).
  3. Calculate Costs: For every range ( [i, j] ), iterate through every possible guess ( x ) in this range and calculate the cost: ( \text{cost} = x + \max(dp[i][x-1], dp[x+1][j]) ). Take the minimum cost for all possible guesses.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        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] = min(x + max(dp[start][x - 1], dp[x + 1][end]) for x in range(start, end))

        return dp[1][n]

Time Complexity

The time complexity of this solution is ( O(n^3) ), where ( n ) is the given integer.

Summary

  • Employ a dynamic programming approach to solve the problem.
  • Start by finding solutions for smaller ranges and build up to the entire range ( [1, n] ).
  • At each step, calculate the costs for all possible guesses and find the minimum.
  • The result is stored in ( dp[1][n] ), representing the minimum cost to guess the number between 1 and ( n ).