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
 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 ).
 BottomUp Approach: Use a bottomup approach to fill the table, starting from smaller ranges and building up to the range ( [1, n] ).
 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][x1], dp[x+1][j]) ). Take the minimum cost for all possible guesses.
Implementation


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 ).