算法1DP

需要初始化：

只有一个鸡蛋时候，区间长度为i，则最坏都要试i次。

区间长度为1时，不管多少个鸡蛋，都只需要试1次

$ 时间复杂度O(N^2M),空间复杂度O(NM)$

参考文献

算法辅导课

AC代码

#include <iostream>
using namespace std;

const int N = 110, M = 15;

int n, m;
int f[N][M];

int main(){

    while (cin >> n >> m){
        //初始化   
        for (int i = 1 ; i <= n ; i ++) f[i][1] = i;
        for (int i = 1 ; i <= m ; i ++) f[1][i] = 1;
        //DP
        for (int i = 2 ; i <= n ; i ++){
            for (int j = 2 ; j <= m ; j ++){
                f[i][j] = f[i][j - 1];
                for (int k = 1 ; k <= i ; k ++){
                    f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1);
                }
            }
        }

        cout << f[n][m] << endl;
    }
    return 0;    
}

算法2DP

$ 时间复杂度O(NM),空间复杂度O(NM)$

根据状态转移方程,空间可以压缩到一维

参考文献

算法辅导课

AC代码

#include <iostream>
using namespace std;

const int N = 110, M = 15;

int n, m;
int f[N][M];

int main(){

    while (cin >> n >> m){
        //DP
        for (int i = 1 ; i <= n ; i ++){
            for (int j = 1 ; j <= m ; j ++)
                f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;
            if (f[i][m] >= n){
                cout << i << endl;
                break;
            }
        }

    }
    return 0;    
}