DP（也是一切优化的基础）

时间复杂度：$O(k\ast n\ast n)$

class Solution {
    
    int N = 10010;
    int K = 110;
    public int superEggDrop(int k, int n) {
    
        int[][] f = new int[K][N];
        for(int j = 1; j <= n; j++) f[1][j] = j;

        for(int i = 2; i <= k; i++) {
    
            for(int j = 1; j <= n; j++) {
    
                int res = N;
                for(int t = 1; t <= j; t++) {
    
                    // t 的选择对应最优策略，策略应选择最优，所以是min
                    // 每种策略下，有多种可能（这里有两种可能），选择最差情况。
                    res = Math.min(res, Math.max(f[i - 1][t - 1], f[i][j - t]) + 1);
                }
                f[i][j] = res;
            }
        }
        return f[k][n];
    }
}

二分（决策单调性）优化

必须要认识到一点的是，$f(k,n)$是关于n的单调不减（或者说非严格单调增）函数。

class Solution {
    
    int N = 10010;
    int K = 110;
    public int superEggDrop(int k, int n) {
    
        int[][] f = new int[K][N];
        for(int j = 1; j <= n; j++) f[1][j] = j; // 初始化; 且f[x][0] = 0;
        for(int i = 2; i <= k; i++) {
    
            int key = 1;
            for(int j = 1; j <= n; j++) {
    
                // f[i - 1][t - 1]、f[i][j - t])
                while(key <= j && f[i - 1][key - 1] <  f[i][j - key]) {
    
                    ++key;
                }
                int res = f[i][j - (key - 1)]; // 两个临界点
                if(key <= j) {
    
                    res = Math.min(res, f[i - 1][key - 1]);
                }
                f[i][j] = res + 1;
            }
        }
        return f[k][n];
    }
}

参考链接

李永乐-双蛋问题-讲解

887. 鸡蛋掉落

1884. 鸡蛋掉落-两枚鸡蛋

动态规划O(n²) + 数学推导O(1)