We are playing the Guessing Game. The game will work as follows:


	I pick a number between&nbsp;1&nbsp;and&nbsp;n.
	You guess a number.
	If you guess the right number, you win the game.
	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.
	Every time you guess a wrong number&nbsp;x, you will pay&nbsp;x&nbsp;dollars. If you run out of money, you lose the game.


Given a particular&nbsp;n, return&nbsp;the minimum amount of money you need to&nbsp;guarantee a win regardless of what number I pick.

&nbsp;
Example 1:

Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
&nbsp;   - If this is my number, your total is $0. Otherwise, you pay $7.
&nbsp;   - If my number is higher, the range is [8,10]. Guess 9.
&nbsp;       - If this is my number, your total is $7. Otherwise, you pay $9.
&nbsp;       - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
&nbsp;       - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
&nbsp;   - If my number is lower, the range is [1,6]. Guess 3.
&nbsp;       - If this is my number, your total is $7. Otherwise, you pay $3.
&nbsp;       - If my number is higher, the range is [4,6]. Guess 5.
&nbsp;           - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
&nbsp;           - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
&nbsp;           - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
&nbsp;       - If my number is lower, the range is [1,2]. Guess 1.
&nbsp;           - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
&nbsp;           - 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:&nbsp;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:&nbsp;There are two possible numbers, 1 and 2.
- Guess 1.
&nbsp;   - If this is my number, your total is $0. Otherwise, you pay $1.
&nbsp;   - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 200


class Solution:
    def getMoneyAmount(self, n):
                        # For an interval [l,r], we choose a num, which if incorrect still
                        # allows us to know whether the secret# is in either [l,num-1] or
                        # [num+1,r]. So, the worst-case (w-c) cost is
                        #
                        #      num + max(w-c cost in [l,num-1], w-c cost in [num+1,r])
                        # 
                        # We do this by recursion and binary search, starting with [1,n].

        @lru_cache(None)              # <-- we cache function results to avoid recomputing them
        def dp(l = 1, r = n)-> int:
            if r-l < 1: return 0      # <-- base case for the recursion; one number in [l,r]       
            ans = 1000                # <-- the answer for n = 200 is 952
            
            for choice in range((l+r)//2,r):
                ans = min(ans,choice+max(dp(l,choice-1),dp(choice+1,r)))

            return ans

        return dp()
class Solution {
    public int getMoneyAmount(int n) {
        int dp[][]=new int[n+1][n+1];
        for(int a[]:dp){
            Arrays.fill(a,-1);
        }
        return solve(1,n,dp);
    }
    static int solve(int start,int end,int[][] dp){
    if(start>=end) return 0;
    if(dp[start][end]!=-1) return dp[start][end];
    int min=Integer.MAX_VALUE;
    for(int i=start;i<=end;i++){
    min=Math.min(min,i+Math.max(solve(start,i-1,dp),solve(i+1,end,dp)));
    }
    dp[start][end]=min;
    return min;
    }
}
class Solution {
public:
    vector<vector<int>> dp;

    int solve(int start, int end)
    {
        if(start>= end)
            return 0;

        if(dp[start][end] != -1)
            return dp[start][end];

        int ans = 0;
        int result = INT_MAX;
        for(int i=start; i<=end; i++)
        {
            int left = solve(start,i-1);
            int right = solve(i+1,end);
            ans = max(left,right) + i; // this line gurantee to include the money that is needed to win higher values
            result = min(ans,result);
        }

        return dp[start][end] = result;
    }

    int getMoneyAmount(int n) {
        int ans = 0;
        dp = vector<vector<int>>(n+1,vector<int>(n+1,-1));
        return solve(1,n);
    }
};
/** https://leetcode.com/problems/guess-number-higher-or-lower-ii/
 * @param {number} n
 * @return {number}
 */
var getMoneyAmount = function(n) {
  // Memo
  this.memo = new Map();
  
  return dp(n, 0, n);
};

var dp = function(n, start, end) {
  let key = `${start}_${end}`;
  
  // Base, there is only 1 node on this side of the leg, which mean our guess is always correct and it cost nothing so return 0
  if (end - start < 2) {
    return 0;
  }
  
  // Base, there are only 2 nodes on this side of the leg, which mean we only need to pick cheapest guess
  if (end - start === 2) {
    // The `start` will always be smaller so pick `start`, add 1 to account for 0 index
    return start + 1;
  }
  
  // Return from memo
  if (this.memo.has(key) === true) {
    return this.memo.get(key);
  }
  
  // Minimum cost
  let minCost = Infinity;
  
  // Try to arrange the tree's left and right leg and find the cost of each leg
  for (let i = start; i < end; i++) {
    let left = dp(n, start, i);
    let right = dp(n, i + 1, end);
    
    // Cost of current guess, add 1 to account for 0 index
    let curr = i + 1;
    
    // Update cost of current guess, which is the max of left or right leg
    curr = Math.max(left + curr, right + curr);
    
    // Then update the minimum cost for entire tree
    minCost = Math.min(minCost, curr);
  }
  
  // Set memo
  this.memo.set(key, minCost);
  
  return minCost;
};
Guess Number Higher or Lower II