# 经典动态规划问题：高楼扔鸡蛋
**通知：算法可视化编辑器上线，[点击体验](https://labuladong.online/algo/intro/visualize/)！另外，建议你在我的 [网站](https://labuladong.online/algo/) 学习文章，体验更好。**
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [887. Super Egg Drop](https://leetcode.com/problems/super-egg-drop/) | [887. 鸡蛋掉落](https://leetcode.cn/problems/super-egg-drop/) | 🔴
**-----------**
本文要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承本书一贯的作风，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了也不划算。
下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
### 一、解析题目
这是力扣第 887 题「鸡蛋掉落」，我描述一下题目：
你面前有一栋从 1 到 `N` 共 `N` 层的楼，然后给你 `K` 个鸡蛋（`K` 至少为 1）。现在确定这栋楼存在楼层 `0 <= F <= N`，在这层楼将鸡蛋扔下去，鸡蛋**恰好没摔碎**（高于 `F` 的楼层都会碎，低于 `F` 的楼层都不会碎，如果鸡蛋没有碎，可以捡回来继续扔）。现在问你，**最坏**情况下，你**至少**要扔几次鸡蛋，才能**确定**这个楼层 `F` 呢？
也就是让你找摔不碎鸡蛋的最高楼层 `F`，但什么叫「最坏情况」下「至少」要扔几次呢？我们分别举个例子就明白了。
比方说**现在先不管鸡蛋个数的限制**，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？
最原始的方式就是线性扫描：我先在 1 楼扔一下，没碎，我再去 2 楼扔一下，没碎，我再去 3 楼……
以这种策略，**最坏**情况应该就是我试到第 7 层鸡蛋也没碎（`F = 7`），也就是我扔了 7 次鸡蛋。
先在你应该理解什么叫做「最坏情况」下了，**鸡蛋破碎一定发生在搜索区间穷尽时**，不会说你在第 1 层摔一下鸡蛋就碎了，这是你运气好，不是最坏情况。
现在再来理解一下什么叫「至少」要扔几次。依然不考虑鸡蛋个数限制，同样是 7 层楼，我们可以优化策略。
最好的策略是使用二分查找思路，我先去第 `(1 + 7) / 2 = 4` 层扔一下：
如果碎了说明 `F` 小于 4，我就去第 `(1 + 3) / 2 = 2` 层试……
如果没碎说明 `F` 大于等于 4，我就去第 `(5 + 7) / 2 = 6` 层试……
以这种策略，**最坏**情况应该是试到第 7 层鸡蛋还没碎（`F = 7`），或者鸡蛋一直碎到第 1 层（`F = 0`）。然而无论那种最坏情况，只需要试 `log7` 向上取整等于 3 次，比刚才尝试 7 次要少，这就是所谓的**至少**要扔几次。
实际上，如果不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数，但问题是，**现在给你了鸡蛋个数的限制 `K`，直接使用二分思路就不行了**。
比如说只给你 1 个鸡蛋，7 层楼，你敢用二分吗？你直接去第 4 层扔一下，如果鸡蛋没碎还好，你可以把鸡蛋捡起来再去更高的楼层尝试；但如果碎了，你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层 `F` 了。
其实这种情况下只能用线性扫描的方法，从下网上一层层尝试扔鸡蛋，那么最坏情况下需要扔 7 次，算法返回结果应该是 7。
有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？
很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。
如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。
说了这么多废话，就是确保大家理解了题目的意思，而且认识到这个题目确实复杂，就连我们手算都不容易，如何用算法解决呢？
引用本文的文章
- [动态规划穷举的两种视角](https://labuladong.online/algo/fname.html?fname=动归两种视角)
- [实际二分搜索时的思维框架](https://labuladong.online/algo/fname.html?fname=二分运用)
- [最优子结构原理和 dp 数组遍历方向](https://labuladong.online/algo/fname.html?fname=最优子结构)
- [经典动态规划：戳气球](https://labuladong.online/algo/fname.html?fname=扎气球)
**＿＿＿＿＿＿＿＿＿＿＿＿＿**
本文为会员内容，请扫码关注公众号或 [点这里](https://labuladong.online/algo/fname.html?fname=高楼扔鸡蛋问题) 查看：
======其他语言代码======
[887.鸡蛋掉落](https://leetcode-cn.com/problems/super-egg-drop/)
### javascript
**dp状态转移 + 备忘录**
```js
var superEggDrop = function (K, N) {
let memo = {}
let dp = function (K, N) {
// base case
if (K === 1) return N;
if (N === 0) return 0;
// 避免重复计算
let key = K + ',' + N
if (memo[key] !== undefined) {
return memo[key];
}
// 正无穷
let res = Infinity;
// 穷举所有的可能的选择
for (let i = 1; i < N + 1; i++) {
res = Math.min(
res,
Math.max(
dp(K, N - i),
dp(K - 1, i - 1)
) + 1
)
}
// 记入备忘录
memo[key] = res;
return res;
}
return dp(K, N);
};
```
**dp状态转移 + 备忘录 + 二分法**
```js
var superEggDrop = function (K, N) {
let memo = {}
let dp = function (K, N) {
// base case
if (K === 1) return N;
if (N === 0) return 0;
// 避免重复计算
let key = K + ',' + N
if (memo[key] !== undefined) {
return memo[key];
}
// 正无穷
let res = Infinity;
// 穷举所有的可能的选择
// for (let i = 1; i < N + 1; i++) {
// res = Math.min(
// res,
// Math.max(
// dp(K, N - i),
// dp(K - 1, i - 1)
// ) + 1
// )
// }
// 用二分搜索代替线性搜索
let lo = 1, hi = N;
while (lo <= hi) {
let mid = Math.floor((lo + hi) / 2);
let broken = dp(K - 1, mid - 1) // 碎
let not_broken = dp(K, N - mid) // 没碎
// res = min(max(碎，没碎) + 1)
if (broken > not_broken) {
hi = mid - 1
res = Math.min(res, broken + 1)
} else {
lo = mid + 1
res = Math.min(res, not_broken + 1)
}
}
// 记入备忘录
memo[key] = res;
return res;
}
return dp(K, N);
};
```
