Question

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution

The problem of finding the minimum cost of reaching the destination number choosing i as a pivot can be divided into the subproblem of finding the maximum out of the minimum costs of its left and right segments. For each segment, we can continue the process leading to smaller and smaller subproblems. This leads us to the conclusion that we can use DP for this problem.

We need to use a dp matrix, where dp(i, j) refers to the minimum cost of finding the worst number given only the numbers in the range (i, j). Now, we need to know how to fill in the entries of this dp. If we are given a range that contains only a single number k, no matter what the number is the cost of finding that number is always 0 since we always hit the number directly without any wrong guess. Thus, firstly, we fill in all the entries of the dp which correspond to segments of length 1 i.e. all entries dp(k, k) are initialized to 0. Then, in order to find the entries for segments of length 2, we need all the entries for segments of length 1. Thus, in general, to fill in the entries corresponding to segments of length len, we need all the entries of length len-1 and below to be already filled. Thus, we need to fill the entries in the order of their segment lengths. Thus, we fill the entries of dp diagonally.

Now, what criteria do we need to fill up the dp matrix? For any entry dp(i, j), given the current segment length of interest is len i.e. if len=j-i+1, we assume as if we are available only with the numbers in the range (i, j). For a particular pivot, the worst-case cost is cost(i, j) = pivot + max(cost(i, pivot - 1), cost(pivot+1, j)). To guarantee a win, we need to choose the pivot such that the cost is minimized for range (i, j), thus: dp(i,j) = min(pivot + max(dp(i, pivot + 1, dp(pivot + 1, n)))) for pivot in (i, j).

The time complexity is \(O(n^3)\).

class Solution {
    public int getMoneyAmount(int n) {
        if(n == 1) return 0;
        if(n == 2) return 1;

        int[][] dp = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            dp[i][i] = 0; // range(i, i)
        }
        for(int i = 1; i < n; i++) {
            dp[i][i + 1] = i; // range(i, i + 1)
        }
        for(int len = 3; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int cost = Integer.MAX_VALUE;
                int j = i + len - 1;
                for(int pivot = i; pivot <= j; pivot++) {
                    cost = Math.min(cost, pivot + Math.max((pivot - 1 >= i ? dp[i][pivot - 1] : 0), (pivot + 1 <= j ? dp[pivot + 1][j] : 0)));
                }
                dp[i][j] = cost;
            }
        }
        return dp[1][n];
    }
}