375-Guess-Number-Higher-or-Lower-II

原题链接

0x0 题目详情

我们正在玩一个猜数游戏，游戏规则如下： 我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。 每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。 然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

测试用例:

示例: n = 10, 我选择了8. 第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。 第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。 第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。 游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。 给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

0x1 解题思路

这道题刚开始没什么思路。但是学到一招。那么就从最简单的情况开始枚举。说不定一个情况一个情况的写出来就能找到规律了。

• 对于n<2时,我们不用花费任何代价,因为必然一次就能猜中

• 对于n=2,即数的范围为[1,2],很显然我们只需要花费1￥,就一定能得出正确答案。当然我们如果第一次就猜中还不用花钱,但是我们要的我们一定能赢,如果带0￥,第一次猜错后就不能猜了

• 对于n=3,即数的范围为[1,2,3],很显然如果我们第一次就猜中,不用花费任何代价。但是我们要的是必胜,所以我们最多花费2￥,这样就一定能赢

• 对于n=4,即数的范围为1,2,3,4:

  • 如果我们第一次猜1,最多可能的代价是1+3=4,因为第一次猜错的情况就剩3个数,回归到n==3的情况

  • 如果我们第一次猜2,最多的花费是2+3==5,因为如果第一次猜错并且正确的数在2的左侧,花费为2;如果正确的数在2的右边,那么只剩下两个数,回归到n==2的情况,最大的代价是n+1=3,所以总的代价是第一次代价2加上第二次代价3等于5

  • 如果我们第一次猜3,同理最多的代价是左侧的代价1加上第一次猜错的代价3等于4

  • 如果第一次猜4,那么最多的代价是4+2==6

我们已经枚举了n==4的所有情况,所以我们可以认为我们的选择每次都是最优的,所以在上面四种情况,我们只会选择第一次猜1,第二次猜3或者第一次猜3,第二次猜1。为什么?因为我们是极度聪明的,每次的选择都是最优的,这个最优表示即使选择错误,代价也是最小的最优策略。所以我们并不会傻傻的第一次猜4或者2。

所以宏观上基于我们的选择是极度最优的,那么我们只需要把每个数都作为第一个数完整的猜一遍,然后把最小的结果筛选出来即可。但是为了保证我们在一次猜的过程也是必胜的,我们需要在猜错i之后,从i两边的可能代价中选择一个最大的。因为在这一次猜的过程中,我们又会变成最笨的,要保证即使每次都错我们也能赢的花费算出来。

所以这是一个求局部最大全局最小的问题。也就是极小化极大值。

0x2 代码实现

暴力递归:

class Solution {
    public int getMoneyAmount(int n) {
        if(n<2){
            return 0;
        }
        return recur(1,n);

    }
    private int recur(int left,int right){


        if(left>=right){
            return 0;
        }
        if(right-left==1){
            return left;
        }
        if(right-left==2){
            return left+1;
        }
        int result=Integer.MAX_VALUE;
        for(int i=left;i<=right;i++){
            //在一次猜的过程中,在猜错的前提下,从左边的代价和右边的代价选一个最大的
            //因为我们要保证我们以i为开始的一轮猜数是必胜的!
            int temp=Math.max(recur(left,i-1),recur(i+1,right))+i;
            result=Math.min(result,temp);
        }
        return result;
    }
}

动态规划:

class Solution {
    public int getMoneyAmount(int n) {
        if(n<2){
            return 0;
        }
        return recur(n);

    }
    private int recur(int n){
        int[][] dp=new int[n+2][n+2];
        for(int i=1;i<n;i++){
            dp[i][i+1]=i;
        }
        for(int i=1;i<n && (i+2)<=n;i++){
            dp[i][i+2]=i+1;
        }
        for(int i=n-1;i>0;i--){
            for(int j=i+1;j<=n;j++){
                if(dp[i][j]==0){
                    dp[i][j]=Integer.MAX_VALUE;
                }
                for(int k=i;k<=j;k++){
                    int temp=Math.max(dp[i][k-1],dp[k+1][j])+k;
                    dp[i][j]=Math.min(dp[i][j],temp);
                }
            }
        }
        return dp[1][n];
    }
}

0x3 课后总结

注意,这道题的dp数组是一个二维数组,并且最后的答案在二维数组的右上角。那么先从下到上再从左到右或者先从左大右再从下到上填充数组理论上都是没有问题的。

但是注意,我们递归的核心部分是:

for(int i=left;i<=right;i++){
    //在一次猜的过程中,在猜错的前提下,从左边的代价和右边的代价选一个最大的
    //因为我们要保证我们以i为开始的一轮猜数是必胜的!
    int temp=Math.max(recur(left,i-1),recur(i+1,right))+i;
    result=Math.min(result,temp);
}

在这个循环中,i是left逐渐增加到right的。那么如果选择一个先从下到上再从左到右的填充过程,改造出来的代码长下面这样:

for(int j=2;j<=n;j++){
    for(int i=j-1;i>0;i--){

        for(int k=i;k>0;k--){

        }   
    }
}

k的变化是从大到小的,而原始递归中与k对应的变量i是从小变大的。变化方向不一样。所以我们尽量完美改造递归代码,与原始递归保持一致。

如果我们选择先从左大右再从下到上,改造出的代码张下面这样:

for(int i=n-1;i>0;i--){
    for(int j=i+1;j<=n;j++){

        for(int k=i;k<=j;k++){

        }
    }
}

可以看到,k也是从小变大的。

结论:

当填充多维dp数组有多个方向时,尽量选择与原始递归代码的方向一致。

参考文献

1. LeetCode375 猜数字大小 II