Guess Number Higher or Lower II

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.

Hint:

  The best strategy to play the game is to minimize the maximum loss you could possibly face. 
  Another strategy is to minimize the expected loss.
  Here, we are interested in the first scenario.Show More Hint 

Tips:

求MinMax!!

It looks like the complexity is O(n^3) because there are n^2 subproblems, and each subproblem takes O(n) time to compute.

这题要求我们在猜测数字y未知的情况下（1~n任意一个数），要我们在最坏情况下我们支付最少的钱。也就是说要考虑所有y的情况。

我们假定选择了一个错误的数x，（1<=x<=n && x!=y ）那么就知道接下来应该从[1,x-1 ] 或者[x+1,n]中进行查找。 假如我们已经解决了[1,x-1] 和 [x+1,n]计算问题，我们将其表示为solve(L,x-1) 和solve(x+1,n)，那么我们应该选择max(solve(L,x-1),solve(x+1,n)) 这样就是求最坏情况下的损失。总的损失就是 f(x) = x + max(solve(L,x-1),solve(x+1,n))

那么将x从1~n进行遍历，取使得 f(x) 达到最小，来确定最坏情况下最小的损失，也就是我们初始应该选择哪个数。

具体：

我们计算从i开始到i + （l-1）的interval的最小花销。 其中设置l为interval的length，例如[2，3，4]的length为3，所以这个interval是[i, i + (l - 1)];

我们需要建立一个二维的dp数组，其中dp[i][i + (l-1)]表示从数字i开始长度为L的interval之间猜中任意一个数字最少需要花费的钱数。

我们需要遍历每一段区间[i,i+(l-1)]，维护一个全局最小值dp[i][i + (l - 1)]变量，然后遍历该区间中的每一个数字，计算局部最大值costForThisGuess = g + max(dp[j][g - 1], dp[g + 1][i])。其中g为在这个区间内猜测的数。

最后，为了找出这段区间的全局最小值，计算dp[i][i + (l - 1)] = Math.min(dp[i][i + (l - 1)], costForThisGuess)。

值得注意的是，当g==i + (l - 1)，即g为这个区间的最后一个数时，我们是没有第二段区间的，所以在计算costForThisGuess时，需要先判定，如果g==i + (l -1), costForThisGuess = dp[i][g - 1] + g。

最后其实我们要求的区间为[1，n]，所以return dp[1][n];

Code:

public class Solution {
    public int getMoneyAmount(int n) {
        // all intervals are inclusive
        // uninitialized cells are assured to be zero
        // the zero column and row will be uninitialized
        // the illegal cells will also be uninitialized
        // add 1 to the length just to make the index the same as numbers used
        int[][] dp = new int[n + 1][n + 1]; // dp[i][j] means the min cost in the worst case for numbers (i...j)

        // iterate the lengths of the intervals since the calculations of longer intervals rely on shorter ones
        for (int l = 2; l <= n; l++) {
            // iterate all the intervals with length l, the start of which is i. Hence the interval will be [i, i + (l - 1)]
            for (int i = 1; i + (l - 1) <= n; i++) {
                dp[i][i + (l - 1)] = Integer.MAX_VALUE;
                // iterate all the first guesses g
                for (int g = i; g <= i + (l - 1); g++) {
                    int costForThisGuess;
                    // since if g is the last integer, g + 1 does not exist, we have to separate this case
                    // cost for [i, i + (l - 1)]: g (first guess) + max{the cost of left part [i, g - 1], the cost of right part [g + 1, i + (l - 1)]}
                    if (g == i + (l-1)) {
                        costForThisGuess = dp[i][g - 1] + g;
                    } else {
                        costForThisGuess = g + Math.max(dp[i][g - 1], dp[g + 1][i + (l - 1)]);
                    }
                    dp[i][i + (l - 1)] = Math.min(dp[i][i + (l - 1)], costForThisGuess); // keep track of the min cost among all first guesses
                }
            }
        }
        return dp[1][n];
    }
}