经典动态规划问题：高楼扔鸡蛋
通知：数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！另外，建议你在我的 网站 学习文章，体验更好。
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 887. Super Egg Drop | 887. 鸡蛋掉落 | 🔴 |
-----------
本文要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承本书一贯的作风，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了也不划算。
下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
一、解析题目
这是力扣第 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 次。最优策略非常多，而且并没有什么规律可言。
说了这么多废话，就是确保大家理解了题目的意思，而且认识到这个题目确实复杂，就连我们手算都不容易，如何用算法解决呢？
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文为会员内容，请扫码关注公众号或 点这里 查看：
====其他语言代码====
javascript
dp状态转移 + 备忘录
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状态转移 + 备忘录 + 二分法
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);
};