Problem Explanation

In this problem, we are asked to find out how much money we need to have to guarantee a win in a guess game. The rules of the game are very simple - a number is picked between 1 and n (both inclusive) and we keep guessing the number. Each wrong guess costs us the guessed number in dollars. For example, if we guess 5 and the number is not 5, we will pay $5.

The game will continue until we guess the correct number. After each incorrect guess, we will be informed if the number picked is higher or lower than our guessed number.

We have to find a strategy that minimizes the amount of money we may lose. More specifically, we need to determine the worst-case scenario - the most amount of money we would need to have to guarantee a win, regardless of the number picked.

Strategy

This problem can be solved by using a dynamic programming approach. We maintain a 2D dp array where dp[i][j] represents the minimum amount of money needed to guarantee a win for guessing the number between i and j.

Initially, all values in dp[i][j] are set to infinity. We start guessing the numbers one by one from i to j and then update dp[i][j] with minimum of dp[i][j] and maximum of dp[i][k-1] and dp[k+1][j] i.e., the worst case between the two halves (left and right) of k plus the cost k.

Let's see how this strategy works with an example:

For n=10 and the number picked is 8.

1
2
3First round: We guess 5, the number is higher. So, we pay $5.
4Second round: We guess 7, the number is higher. So, we pay $7.
5Third round: We guess 9, the number is lower. So, we pay $9.

So, we end up paying $5+$7+$9 =$21. That's the minimum amount of money we need to guarantee a win, which is the solution to this problem.

Python Solution

1
2Python
3class Solution:
4    def getMoneyAmount(self, n: int) -> int:
5        dp = [[0]*(n+1) for _ in range(n+1)]
6        for length in range(2, n+1):
7            for start in range(n-length+1):
8                minres=float('inf')
9                for piv in range(start+(length//2),start+length):
10                    res = piv+1+max(dp[start][piv-1],dp[piv+1][start+length-1])
11                    minres=min(minres,res)
12                dp[start][start+length-1]=minres
13        return dp[0][n-1]

This Python solution implements the dynamic programming strategy as described above.

Java Solution

1
2Java
3public class Solution {
4    public int getMoneyAmount(int n) {
5        int[][] dp = new int[n+1][n+1];
6        for(int len=2; len<=n; len++) {
7            for(int start=0; start<=n-len; start++) {
8                int minres = Integer.MAX_VALUE;
9                for(int piv=start+(len/2); piv<start+len; piv++) {
10                    int res = piv+1+Math.max(dp[start][piv-1],dp[piv+1][start+len-1]);
11                    minres=Math.min(minres,res);
12                }
13                dp[start][start+len-1]=minres;
14            }
15        }
16        return dp[0][n-1];
17    }
18}

The Java solution is similar to the Python solution and follows the same dynamic programming strategy.

Javascript Solution

1
2Javascript
3var getMoneyAmount = function(n) {
4  let dp = Array(n+1).fill(0).map(()=>Array(n+1).fill(0));
5  for(let len=2; len<=n; len++) {
6    for(let start=0; start<=n-len; start++) {
7      let minres = Number.MAX_SAFE_INTEGER;
8      for(let piv=start+(parseInt(len/2)); piv<start+len; piv++){
9         let res = piv+1+Math.max(dp[start][piv-1],dp[piv+1][start+len-1]);
10         minres = Math.min(minres,res);
11      }
12      dp[start][start+len-1] = minres;
13    }
14  }
15  return dp[0][n-1];  
16};

The Javascript solution also implements the same dynamic programming strategy as the Python and Java solutions.

C++ Solution

1
2C++
3class Solution {
4public:
5    int getMoneyAmount(int n) {
6        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
7        for(int len=2; len<=n; len++){
8            for(int start=0; start<=n-len; start++){
9                int minres = INT_MAX;
10                for(int piv=start+(len/2); piv<start+len; piv++){
11                    int res = piv+1+max(dp[start][piv-1],dp[piv+1][start+len-1]);
12                    minres = min(minres,res);
13                }
14                dp[start][start+len-1] = minres;            
15            }
16        }
17		return dp[0][n-1];
18    }
19};

The C++ solution is same as other solutions and uses the same dynamic programming strategy to find out the minimum amount of money needed to guarantee a win.

C# Solution

1
2csharp
3public class Solution {
4    public int GetMoneyAmount(int n) {
5        int[,] dp = new int[n+1,n+1];
6        for(int len=2; len<=n; len++){
7            for(int start=0; start<=n-len; start++){
8                int minres = int.MaxValue;
9                for(int piv=start+(len/2); piv<start+len; piv++){
10                    int res = piv+1+Math.Max(dp[start,piv-1],dp[piv+1,start+len-1]);
11                    minres = Math.Min(minres,res);
12                }
13                dp[start,start+len-1] = minres;            
14            }
15        }
16		return dp[0,n-1];
17    }
18}

The C# solution also uses the same dynamic programming approach to solve this problem. It's similar to the other solutions, so I won't walk through it here.# Kotlin Solution

1
2kotlin
3fun getMoneyAmount(n: Int): Int {
4    val dp = Array(n+1) { IntArray(n+1) }
5    for(length in 2..n) {
6        for(start in 0..(n - length)) {
7            var minres = Int.MAX_VALUE
8            for(piv in (start + (length / 2)) until start + length) {
9                val res = piv + 1 + maxOf(dp[start][piv - 1], dp[piv + 1][start + length - 1])
10                minres = minOf(minres, res)
11            }
12            dp[start][start + length - 1] = minres
13        }
14    }
15    return dp[0][n-1]
16}

Just like all other solutions, the Kotlin solution uses the dynamic programming approach to solve the problem. This algorithm helps to find the minimum amount of money needed to ensure a win in the guess game.

Ruby Solution

1
2ruby
3def get_money_amount(n)
4  dp = Array.new(n+1) { Array.new(n+1, 0) }
5  for len in 2..n
6    for start in 0..(n-len)
7      minres = Float::INFINITY
8      for piv in (start + (len / 2))...(start + len)
9          res = piv + 1 + [dp[start][piv - 1], dp[piv + 1][start + len - 1]].max
10          minres = [minres, res].min
11      end
12      dp[start][start+ len - 1] = minres
13    end
14  end
15  dp[0][n-1]
16end

The Ruby solution is same as above solutions and it also implements the dynamic programming methodology to get the minimum necessary amount due to bad guessing.

Conclusion

To conclude, for this guessing number game, all solutions follow the dynamic programming strategy and implemented a 2D dp array to get the minimum amount required to ensure the win. All solutions were implemented in different programming languages and proven the consistency of the problem regardless of the language that used. All solutions are effecient and have a time complexity of about O(n^2), which could be considered as a preferable solution for such problem.