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.
- 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 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.
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; }();