In this Leetcode Guess Number Higher or Lower II problem solution, We are playing the Guessing Game. The game will work as follows:

I pick a number between 1 and n.

  1. You guess a number.
  2. If you guess the right number, you win the game.
  3. 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.
  4. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

we have given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

Leetcode Guess Number Higher or Lower II problem solution


Problem solution in Python.

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        @lru_cache(maxsize=None)
        def rec(a, b):
            if b < 5:
                return [0, 0, 1, 2, 4][b]
            elif b == a+2:
                return a+1
            else:
                return min(i + max(rec(a,i-1),rec(i+1,b)) for i in range(b-3, a, -4))
        return rec(1, n)



Problem solution in Java.

class Solution {
    public int getMoneyAmount(int n) {
        if(n == 1)
            return 0;
        if(n == 2)
            return 1;
        int dp[][] = new int [n+2][n+2];
        for(int g=0;g<n;g++){
            for(int i=1,j=g+1;j<=n;j++,i++){
                if(g == 0)
                    dp[i][j] = 0;
                else if(g == 1)
                    dp[i][j] = Math.max(i,j);
                else{
                    int min = Integer.MAX_VALUE;
                    for(int k=i;k<j;k++){
                        min = Math.min(min,Math.max(dp[i][k-1]+k,dp[k+1][j]+k));
                    }
                    dp[i][j] = min;
                }
            }
        }
        return dp[1][n];
    }
}


Problem solution in C++.

class Solution {
public:
    vector<vector<int>> storedResults;
    
    int getMoneyAmount(int n) {
        storedResults.clear();
        storedResults.resize(n+2, vector<int>(n+2, -1));
        
        return calc(1, n);
    }
    
    int calc(int low, int high)
    {
        if (low >= high)
        {
            return 0;
        }
        
        int minCost = INT_MAX;
        
        for (int i = (low + high) / 2; i <= high; ++i)
        {
            int rightCost = storedResults[i+1][high];
            if (rightCost == -1)
            {
                rightCost = calc(i+1, high);
                storedResults[i+1][high] = rightCost;
            }
            int leftCost = storedResults[low][i-1];
            if (leftCost == -1)
            {
                leftCost = calc(low, i-1);
                storedResults[low][i-1] = leftCost;
            }
            
            int cost = i + max(rightCost, leftCost);
            minCost = min(cost, minCost);
        }
        
        return minCost;
    }
};

static auto x = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();