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.

## 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[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;
}();
```