AcWing 1048. 鸡蛋的硬度

题目链接：https://www.acwing.com/problem/content/description/1050/

第一种方式：O(nm)

#include 

using namespace std;
const int N = 110, M = 15;
int f[N][M];
// f[i][j] 表示使用j个鸡蛋测量i的长度

int main()
{
    int n, m;
    while(cin >> n >> m){
        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;
    
}

第二种方式：O(n²m)

#include 

using namespace std;
const int N = 110;
int f[N][N], n, m;
// f[i][j] 表示区间长度为i，使用j个鸡蛋来进行测

int main()
{
    while(cin >> n >> m){
        for(int i = 1; i <= n; i++) f[i][1] = i;
        for(int j = 1; j <= m; j++) f[1][j] = 1;
        
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++){
                f[i][j] = f[i][j - 1];  //表示不用第j个鸡蛋
                for(int k = 1; k <= i; k++)
                    f[i][j] = min(f[i][j], max(f[k - 1][j - 1] + 1, f[i - k][j] + 1));
            }
        }
        cout << f[n][m] << endl;
    }
    return 0;
}