李永乐老师的双蛋问题

#include<iostream>
using namespace std;
const int N=100+10;
const int INF=0x7fffffff;
int main(){
    int n,m;
    while(cin>>n>>m){
        int dp[N][N]={0};//dp[i][j]表示的是i层的j个鸡蛋，最坏情况下需要扔的次数
        //下面首先进行的是初始化
        //当只有一个鸡蛋的时候，最坏情况下需要扔的鸡蛋数是楼层数，因为其他的情况有找不到那一层蛋碎的可能。
        for(int i=1;i<=n;i++)dp[i][1]=i;
        //下面的初始化表示的是，只有一层那么最坏情况下需要扔鸡蛋的次数，很明显不管你有多少个鸡蛋，只需要扔一次就可以啦。
        for(int i=1;i<=m;i++)dp[1][i]=1;
        //下面是主循环
        for(int i=2;i<=n;i++){
            for(int j=2;j<=m;j++){
                dp[i][j]=INF;//因为要求最小的值，所以初始化为一个很大的值。
                //下面是关键的状态转移方程。意思是：
                //我现在更新前i层，我们动态规划是每一层，每一个鸡蛋都要遍历的。
                //1~i层楼可以扔鸡蛋，当在扔到1-i这个范围内的第k层的时候，我们有两种情况出现：
                //1.蛋碎了，那么我们就知道蛋不会碎只能在k-1层之前，我们还可以使用的蛋数目是j-1个
                //2.蛋没有碎，那么我们的搜索区间变成k+1~i之间，问题规模变成i-k，鸡蛋还可以接着使用
                //加一：含义是扔了一次鸡蛋
                for(int k=1;k<=i;k++){
                    dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
    
    return 0;
}