猜数游戏（求保证能赢的最少钱数）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:

1. 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 thefirst scenario.
2. Take a small example (n = 3). What do you end up paying in the worst case?
3. Check out this article if you're still stuck.
4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

【题意】猜数游戏，要求你猜错了就得付与你所猜的数目一致的钱，最后应求出保证你能赢的钱数(即求出保证你获胜的最少的钱数)。

① 在1-n个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(w(1 ,i-1), w(i+1 ,n))，这里w(x,y))表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，求出其中的最小值即为答案，即最小的最大值问题。http://blog.csdn.net/adfsss/article/details/51951658

设dp[i][j]为当范围为(i + 1，j + 1)时，能够保证获胜的最少钱数。

则有dp[i][j] = k + max(dp[i][k - 1],dp[k + 1][j]);

class Solution { //16ms
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0;i < n + 1;i ++){
            dp[i] = new int[n + 1];
        }
        for (int i = 0;i < n + 1;i ++){//初始化
            for (int j = 0;j < n + 1;j ++){
                dp[i][j] = 0;
            }
        }
        return cost(dp,1,n);
    }
    public int cost(int[][] dp,int i,int j){
        int res = Integer.MAX_VALUE;
        if (i >= j){
            return 0;
        }
        if (dp[i][j] != 0){
            return dp[i][j];
        }
        for (int k = i;k < j + 1;k ++){
            int tmp = k + Math.max(cost(dp,i,k - 1),cost(dp,k + 1,j));
            if (tmp < res){
                res = tmp;
            }
        }
        dp[i][j] = res;
        return res;
    }
}

② 进化版。

class Solution { //4ms
    int[][] dp;
    public int getMoneyAmount(int n) {
        dp = new int[n + 1][n + 1];
        return cost(1,n);
    }
    public int cost(int i,int j){
        if (i >= j){
            return 0;
        }
        if (i >= j - 2){
            dp[i][j] = j - 1;
            return dp[i][j];
        }
        if (dp[i][j] != 0){
            return dp[i][j];
        }
        int mid = (i + j) / 2 - 1;
        int min = Integer.MAX_VALUE;
        while(mid < j){
            int left = cost(i,mid - 1);
            int right = cost(mid + 1,j);
            min = Math.min(min,mid + Math.max(left,right));
            if (right <= left) break;
            mid ++;
        }
        dp[i][j] = min;
        return dp[i][j];
    }
}