动态规划——楼层扔鸡蛋问题

前言

大一的时候蓝桥杯省赛遇到过(作为非编程题的压轴题),这次看的别人的面经也多次出现,就写篇博文总结一下。

题目

有一栋楼共100层,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡蛋,设计方案找出N,并且保证在最坏情况下,最小化鸡蛋下落的次数。

解析

无脑二分法(最多人想到的伪解法)

当时省赛没注意审题,就想的这种方法,首先需要确定的是,在最坏的情况下,求最小化尝试次数,所以肯定不是无脑二分那么简单了。
例如,你第一次扔第50层,碎了如果你再选择二分,直接到25层又碎的话,两个鸡蛋就都没了,接下来你咋试啊?
所以你接下来只能从1层到49层一个一个试了,最终尝试次数为50次。

假设法

首先,假设答案,也就是最小尝试次数为x,此时从第x层开始扔,有两种情况:

  • 碎了,那么只能从1到x-1一个一个试了,加上前面扔的一次,总结果为x次,符合,这也是为什么选择第x层的原因,如果选择其他层,又碎了的话,则最小尝试次数肯定不等于x,这就与假设相悖了。
  • 没碎,那么直接把第1到x层抛弃掉,当作不存在(因为鸡蛋不会在这范围内碎掉),我们把第x+1层当成第1层,尝试次数为x-1(因为刚刚扔了1次,最小尝试次数减1),此时就从第x-1层(真实层数为x+x-1)开始扔,同样又会出现两种情况:
  • 第二次碎了,则是从第1层到第x-2层开始扔 ,总尝试次数同样是x
  • 第二次没碎,还是之前原理,这次从x-2层开始,以此类推,一直扔到最后一层或碎了为止。

最终结果就是\(x+(x-1)+(x-2)...+1 = 100\),解得\(x = 14\)。

题目升级版本

楼层M,鸡蛋数N,求最坏情况下的最小次数。

动态规划法

理解了上面的假设法,再学过动态规划的话,这里应该就问题不大了。
状态转移方程如下:

[f[m][n] = min(f[m][n],1+max(f[k-1][n-1],f[m-k][n]),k\in[1,m-1]) ]

解释:当有n个鸡蛋时,所需尝试的楼层数为m,此时将鸡蛋扔在第k层,则有两种情况

  • 碎了,那么接下来只需要尝试1到k-1层,鸡蛋数为n-1,此时问题不就转化成了楼层数k-1,鸡蛋数n-1,求最坏情况下的最小次数吗?
  • 没碎,那么直接把第1到k层抛弃掉,只需要尝试第k+1到m层,鸡蛋没碎,所以扔为n,此时问题不就转化成了楼层数m-k,鸡蛋数n,求最坏情况下的最小次数吗?
  • 为什么取MAX?因为是最坏的情况,所以取碎了与没碎中的最大情况。

代码如下:

int superEggDrop(int egg,int floor){
    int ans[floor+1][egg+1];
    for(int m = 1;m <= floor;m++)
        for(int n = 1;n <= egg;n++)
            ans[m][n] = m;//最坏的情况下,自然是所有楼层试一遍,同时这也是鸡蛋数为1时的答案

    for(int m = 1;m <= floor;m++)
        for(int n = 2;n <= egg;n++)//n必须从2开始,如果是1,就会出现ans[k-1][1-1=0],显然不存在0鸡蛋的情况
            for(int k = 1;k <= m-1;k++)
                ans[m][n] = min(ans[m][n],1+max(ans[k-1][n-1],ans[m-k][n]));
    return ans[floor][egg];
}

然而,该解法的时间复杂度为\(O(km^2)\),空间复杂度为\(O(mn)\),显然还可以继续优化。

动态规划+二分优化

对于\(f[k-1][n-1]\)和\(f[m-k][n]\),当在第三重循环中,\(m,n\)不变,我们可以将其当作系数,只有\(k\)在\([1,m-1]\)的范围内一直增加,而\(k\)又与楼层数有关,显然,当楼层数增加时,测试次数一定增加(100层和101层,显然100更有利吧?)。
而\(f[k-1][n-1]\)和\(f[m-k][n]\),前者\(k\)系数为正,后者\(k\)系数为负,一个递增,一个递减,我们就可以找二分它们的交点,使得无论碎不碎,它们的测试结果都相同,使得时间复杂度为\(O(kmlogm)\)。

int superEggDrop(int egg,int floor){
    int ans[floor+1][egg+1];//鸡蛋数只需要考虑两种情况
    for(int m = 1;m <= floor;m++)
        for(int n = 1;n <= egg;n++)
            ans[m][n] = m;//最坏的情况下,自然是所有楼层试一遍,同时这也是鸡蛋数为1时的答案

    for(int m = 2;m <= floor;m++)//当楼层数为1时,结果必然是1
        for(int n = 2;n <= egg;n++){//n必须从2开始,如果是1,就会出现ans[k-1][1-1=0],显然不存在0鸡蛋的情况
            int l = 1,r = m;//范围是[l,r)
            while(l+1 < r){
                int k = (l+r)/2;
                int l_value = ans[k-1][n-1];
                int r_value = ans[m-k][n];
                if (l_value == r_value){
                    l = k;
                    break;
                }
                else if (l_value > r_value) r = k;
                else l = k+1;
            }
            ans[m][n] = min(ans[m][n],1+max(ans[l-1][n-1],ans[m-l][n]));
        }
    return ans[floor][egg];
}

当然了,现在还不是最优解,由于时间问题,这里就不再赘述,有兴趣的可以自行百度。

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。