DP笔记(19)：高楼扔鸡蛋（鸡蛋掉落）
Author：zhoulujun Date：
高楼扔鸡蛋
1884. 鸡蛋掉落-两枚鸡蛋 https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/description/
887. 鸡蛋掉落 https://leetcode.cn/problems/super-egg-drop/description/
题目的详细内容如下：
1884. 鸡蛋掉落-两枚鸡蛋
给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。
每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
887. 鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
可以看到，2题的区别就是给鸡蛋个数不同
解题思路分析
如果只有1个鸡蛋，那么就是从第一层开始扔，最多扔n次。
如果有无限个鸡蛋，直接上二分查找就行
如果只有2个鸡蛋，需要怎么考虑？
如果只有k个鸡蛋，有需要怎么考虑？
2个鸡蛋
只有2个鸡蛋的情况下，直接使用二分查找，比如100层的情况下，50层丢下刚好碎了，那么剩下一个鸡蛋就只能从第一层爱是扔。
这个样做肯定不是最有效的。那么我们可以如何做呢？
1、改进二分法，设计更加合理的分割……
2、递推，从2层开始扔，然后再4层开始扔，基于这种模式进行改进
基于第一种模式，可以看李永乐老师的：https://www.youtube.com/watch?v=mLV_vOet0ss
基于第二种模式，动态规划就是一个很好的解决办法。
而且，可以解决k个鸡蛋n层楼的问题
function superEggDrop(K, N) {
// dp[i][j] 表示有 i 个鸡蛋，面对 j 层楼时所需的最小尝试次数
let dp = new Array(K + 1).fill(0).map(() => new Array(N + 1).fill(0));
for (let i = 1; i <= K; i++) {// 初始化边界条件
dp[i][1] = 1; // 只有一个楼层时，只需试一次
}
for (let j = 1; j <= N; j++) {
dp[1][j] = j; // 只有一个鸡蛋时，需要试 j 次
}
// 填充DP表
for (let i = 2; i <= K; i++) {
for (let j = 2; j <= N; j++) {
dp[i][j] = Infinity;
for (let x = 1; x <= j; x++) {
let broken = dp[i - 1][x - 1]; // 鸡蛋碎了，剩下 i-1 个鸡蛋，还剩 x-1 层楼
let notBroken = dp[i][j - x]; // 鸡蛋没碎，还有 i 个鸡蛋，剩余 j-x 层楼
dp[i][j] = Math.min(dp[i][j], Math.max(broken, notBroken) + 1);
}
}
}
return dp[K][N];
}上面的解法不是最好的，但是应该是最容易懂的
转载本站文章《DP笔记(19)：高楼扔鸡蛋（鸡蛋掉落）》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9193.html