```java
package dp.superEggDrop;
/**
* 887. 鸡蛋掉落
* 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
* <p>
* 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
* <p>
* 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
* <p>
* 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
* <p>
* <p>
* 示例 1：
* <p>
* 输入：k = 1, n = 2
* 输出：2
* 解释：
* 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
* 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
* 如果它没碎，那么肯定能得出 f = 2 。
* 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
* 示例 2：
* <p>
* 输入：k = 2, n = 6
* 输出：3
* 示例 3：
* <p>
* 输入：k = 3, n = 14
* 输出：4
* <p>
* <p>
* 提示：
* <p>
* 1 <= k <= 100
* 1 <= n <= 104
*/
public class superEggDrop {
// 考虑每一层扔鸡蛋，扔下去的结果两种，碎、不碎
// 如果碎了，说明F在0~i-1之间，还需要在1~i-1即i-1层楼中搜索
// 如果没有碎，说明F在i~N之间，还需要再i+1~N层即N-i层楼中搜索
// 记dp[i][k]表示有k个鸡蛋，i层楼中确定F的具体值的最小搜索次数
// 那么，假设某次搜索在第j楼，根据上面的思路，在第j楼扔下，存在两种结果：碎、不碎
// 然后根据结果分别在j楼上面或者下面的搜索区间继续搜索F的值
// 因此可以得到递推公式
// dp[i][k] =min{ max(dp[j-1][k-1], dp[i-j][k]) + 1 | 1<=j<=i }
// 显然，k>=1，而i为0时，表示没有任何楼层，那么dp[0][k]=0
// 当k=1，只有一个鸡蛋，只能线性搜索，dp[i][1]=i
public static int superEggDrop(int k, int n) {
int[][] dp = new int[k + 1][n + 1];
for (int i = 0; i <= n; i++) {
dp[1][i] = i;
}
for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
Integer res = Integer.MAX_VALUE;
for (int l = 1; l <= j; l++) {
res = Math.min(res, Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);
}
dp[i][j] = res;
}
}
return dp[k][n];
}
public static void main(String[] args) {
System.out.println(superEggDrop(2, 6));
}
}
```
.;
{
( , ) {
[][] [ ][ ];
( ; ; ) {
[][] ;
}
( ; ; ) {
( ; ; ) {
.;
( ; ; ) {
.(, .([ ][ ], [][ ]) );
}
[][] ;
}
}
[][];
}
([] ) {
..((, ));
}
}
