李永乐老师讲的： 双蛋问题 $O(n^2m)$
闫学灿老师讲的： 鸡蛋的硬度 $O(nm)$

共有 $n$ 层楼，$m$ 个鸡蛋，没碎的鸡蛋可以重复使用

求最少要多少次可以求出鸡蛋摔碎的临界楼层？

题目链接： 鸡蛋的硬度

很久以前就听说过这个题了，据说是谷歌面试题，也是一个动态规划的经典问题

但是一直都没有尝试去做

看了李永乐老师的讲解之后试着写了一下

有一些边界问题没有细考虑，但是对上了这个表

时间复杂度：$O(n^{2}m)$

C++代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 1010, INF = 1e9;

int n, m;
int f[N][N];        //  f[i][j]表示共i层楼j个鸡蛋时最少要试几次保证能找到临界点

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++)
    {
        //  楼层数为i时，鸡蛋数量为1时，需要从低到高遍历，共i次
        f[i][1] = i;

        for(int j = 2; j <= m; j ++)
        {
            //  要求最小值时，先反向赋一个很大的值
            f[i][j] = INF;

            //  遍历鸡蛋扔在的k层的情况
            for(int k = 1; k <= i; k ++)
                /*  
                    设临界值为t
                    f[k - 1][j - 1]为鸡蛋碎了，t在[1, k]这个区间中，共k层，剩余j - 1个鸡蛋
                    f[i - k][j]为鸡蛋未碎，t在[k + 1, i]这个区间中，共i - k层，剩余j个鸡蛋
                    在两种情况中取较大值（考虑最坏情况）加上本次，更新f[i][j]
                */
                f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1);
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
            printf("%6d", f[i][j]);
        puts("");
    }
    return 0;
}