1.题目

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 f 确切的值的最小操作次数 是多少？

示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

示例 2：
输入：k = 2, n = 6
输出：3

示例 3：
输入：k = 3, n = 14
输出：4

提示：
1 <= k <= 100
1 <= n <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop

2.思路

（1）动态规划
思路参考经典动态规划：高楼扔鸡蛋。

3.代码实现（Java）

//思路1————动态规划
public int superEggDrop(int k, int n) {
    //k:鸡蛋个数   n:楼层数
    /*
        dp[i][j] = m, 
        当前有 i 个鸡蛋，可以尝试扔 j 次鸡蛋，最坏情况下最多能确切测试⼀栋 m 层的楼
        m ≤ n:在最坏情况下，即线性扫描一栋 n 层的楼
    */
    int[][] dp = new int[k + 1][n + 1];
    int j = 0;
    //当dp[k][j] == n时结束循环
    while (dp[k][j] < n) {
        //增加扔鸡蛋的次数
        j++;
        for (int i = 1; i <= k; i++) {
            /*
                第 i 层楼扔了鸡蛋之后，可能出现以下两种情况：
                (1)鸡蛋碎了，那么鸡蛋的个数 k 应该减一，搜索的楼层区间应该从 [1...n] 变为[1..i - 1]，共 i - 1 层楼
                (2)鸡蛋没碎，那么鸡蛋的个数 k 不变，搜索的楼层区间应该从 [1...n] 变为 [i + 1..n]，共 n - i 层楼
                鸡蛋碎了测楼下，没碎测楼上
                无论上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）
            */
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1;
        }
    }
    //返回最小操作次数（扔鸡蛋的次数）
    return j;
}