区间动态规划-扔鸡蛋

题目：
你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？
鸡蛋没有撞碎可以重复用，每个鸡蛋的抗摔能力一样，鸡蛋可以有剩余。

最好的策略是使用二分查找思路，我先去第 (1 + 10) / 2 = 5层扔一下：
如果碎了说明 F 小于 4，我就去第 (1 + 4) / 2 = 2 层试……
如果没碎说明 F 大于等于 4，我就去第 (5 + 10) / 2 = 7 层试……

实际上，如果不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数，但问题是，现在给你了鸡蛋个数的限制 K，直接使用二分思路就不行了。

比如说只给你 1 个鸡蛋，710层楼，你敢用二分吗？你直接去第 45层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层 F 了。这种情况下只能用线性扫描的方法，算法返回结果应该是 10。

有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？

很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。
如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。
最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。

代码实现：

/**************************************************************** 
 * Description: 扔鸡蛋问题   egg dropping
 * Author: Alex Li
 * Date: 2023-05-21 16:28:22
 * LastEditTime: 2023-08-15 17:28:46
****************************************************************/
#include <algorithm>
#include <iostream>
#include <limits>
using namespace std;

const int MAXN=105;
const int MAXK=105;

int h[MAXN][MAXK];

//递归方法
int f(int n, int m){
    if(m==1)return n;
    if(n==0)return 0;

    int ret=numeric_limits<int>::max();
    for (int i =1; i <=n; i++)
       ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);
    return ret;        
    }
//递推方法
int g(int n,int m){
    for (int i =1; i <=n; i++)
        h[i][1]=i;
    for (int j =1; j <=m; j++)
        h[0][j]=0;
    
    for (int i = 1; i <=n; i++){
        for (int j =2; j <=m; j++){
            h[i][j]=numeric_limits<int>::max();
            for(int k=1;k<=i;k++)
                h[i][j]=min(h[i][j],max(h[i-k][j],h[k-1][j-1])+1);
        }
    }
    return h[n][m];
}

int main(){
    int n,m;// n为楼层，n为鸡蛋个数
    cin>>n>>m;
    cout<<f(n,m)<<endl<<g(n,m)<<endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

区间动态规划-扔鸡蛋