鸡蛋落地问题

https://leetcode-cn.com/problems/super-egg-drop/
n 层楼，k个鸡蛋，如何确定那一层楼扔下鸡蛋会碎，最少尝试多少次。

法一

状态定义：为 n 层楼扔下 k 个鸡蛋的最少次数。
转移：尝试枚举第一个扔鸡蛋的楼层

• 如果碎掉，问题变为
• 如果没有碎掉：问题变为

状态转移：
复杂度：
由于随着 n 的增加（k 一定），答案增加，所以第一部分递增，第二部分递减。
我们期望找到 的最小值，那么就是找到这两个函数的交点。
找到最大的 有
找到最小的 有
那么最终答案在 和 中做选择即可。

以下代码采用递推法，如果改成记忆化，对于LC测试会快一些。

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<vector<int>> d(n + 1, vector<int>(k + 1, 1E9));
        for(int j = 0; j <= k; j++) d[0][j] = 0;
        for(int j = 1; j <= k; j++) d[1][j] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= k; j++){
                int l = 1, r = i;
                while(l < r) {
                    int m = (l + r + 1) / 2;
                    if(d[m - 1][j - 1] <= d[i - m][j]) l = m;
                    else r = m - 1;
                }
                int x0 = l;
                l = 1, r = i;
                while(l < r) {
                    int m = (l + r) / 2;
                    if(d[m - 1][j - 1] >= d[i - m][j]) r = m;
                    else l = m + 1;
                }
                int x1 = l;
                int val1 = max(d[x0 - 1][j - 1], d[i - x0][j]) + 1;
                int val2 = max(d[x1 - 1][j - 1], d[i - x1][j]) + 1;
                d[i][j] = min(d[i][j], min(val1, val2));
            }
        }
        return d[n][k];
    }
};

法二

注意观察，固定 k，随着 n 的增加，x 应当是增加的。
所以利用决策单调性求解即可，复杂度

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<int> d(n + 1);
        iota(d.begin(), d.end(), 0);
        for(int j = 2; j <= k; j++){
            vector<int> f(n + 1);
            int x = 1;
            f[1] = 1;
            for(int i = 2; i <= n; i++){
                while(x < i && max(d[x - 1], f[i - x]) >= max(d[x], f[i - x - 1])) x++;
                f[i] = max(d[x - 1], f[i - x]) + 1;
            }
            d = move(f);
        }
        return d[n];
    }
};

法三

表示 k 个鸡蛋尝试 t 次能够最多测试多少层。
随便扔一下，如果碎了，那么说明下面最多有 层，如果没碎，说明上面最多可以有 层。
所以

class Solution {
public:
    int superEggDrop(int k, int n) {
        if(n == 1) return 1;
        vector<vector<int>> f(n + 1, vector<int>(k + 1));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++){
                f[i][j] = 1 + f[i - 1][j] + f[i - 1][j - 1];
            }
            if(f[i][k] >= n) return i;
        }
        return n;
    }
};