google一道面试题的扩展——智力挑战

google曾有个面试题说给你两个鸡蛋，在一个100层楼上测试鸡蛋掉下摔碎的临界高度，以楼层计算，问你最少的尝试次数。

当时因为只有两个鸡蛋所以答案很简单那就是14次。

思路如下：假设至少需要尝试x次，则第一次在第x层扔下，如果摔碎了，则还有一个鸡蛋则最大需要再逐个尝试1-（x-1）层即可，若未摔碎，则此时还是两个鸡蛋，只需要在x+（x-2）层扔即可，因为这样如果碎了，只需要尝试x-2次，如果没碎则需要再尝试x-2次，一次类推，两个鸡蛋可检测的楼层为x+(x-2)+(x-3)+…+1层时，检测次数最小为x次，另x+(x-2)+(x-3)+…+1>=100即可算出x最小为14，现在扩展一下，假设有n个鸡蛋m层楼，问你至少需要多少次尝试就能测出鸡蛋的临界高度。

请编程实现。

分析这其实是一个动态规划问题，dp[i][j]为i个鸡蛋在j层楼需要最少尝试的次数，状态转移题目中有解释。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int M=200;
const int N=200;

int dp[M+1][M+1];

int main ()
{
    int m,n;
    memset(dp,0,sizeof(dp));
    for (int i=1;i<=N;i++)
    {
        dp[1][i]=i;
    }
    for (int i=2;i<=M;++i)
    {
        for (int j=1;j<=N;++j)
        {
            dp[i][j]=1+dp[i][j-1];
            for (int k=2;k<=j;++k)
            {   //此处dp[i-1][k-1]表示第k层扔鸡蛋碎了则还有i-1个鸡蛋需要最多尝试k-1层(1-i-1)
                //dp[i][j-1]表示第k层扔鸡蛋没碎，则还有i个鸡蛋只需要尝试k+1到j层即可所以为j-k层
                //这两种情况选出最坏情况加上本次操作即可
                dp[i][j]=min(dp[i][j],1+max(dp[i-1][k-1],dp[i][j-k]));
            }
        }
    }
    while (scanf("%d%d",&m,&n)!=EOF)
    {
        printf("%d\n",dp[m][n]);
    }
    return 0;
}