高楼扔鸡蛋问题.md

# 经典动态规划问题：高楼扔鸡蛋

<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.github.io/algo/images/souyisou1.png)

**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0；[第 13 期刷题打卡](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 最后一天报名！另外，建议你在我的 [网站](https://labuladong.github.io/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。

有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？

很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。

如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次​。最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。

说了这么多废话，就是确保大家理解了题目的意思，而且认识到这个题目确实复杂，就连我们手算都不容易，如何用算法解决呢？



<hr>
<details>
<summary><strong>引用本文的文章</strong></summary>

 - [二分搜索怎么用？我又总结了套路](https://labuladong.github.io/article/fname.html?fname=二分运用)
 - [二分搜索怎么用？我和快手面试官进行了深度探讨](https://labuladong.github.io/article/fname.html?fname=二分分割子数组)
 - [动态规划问题的两种穷举视角](https://labuladong.github.io/article/fname.html?fname=动归两种视角)
 - [最优子结构原理和 dp 数组遍历方向](https://labuladong.github.io/article/fname.html?fname=最优子结构)
 - [经典动态规划：戳气球](https://labuladong.github.io/article/fname.html?fname=扎气球)

</details><hr>





**＿＿＿＿＿＿＿＿＿＿＿＿＿**

应合作方要求，本文不便在此发布，请扫码关注回复关键词「鸡蛋」或 [点这里](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_6298795de4b01a4852072fa7/1) 查看：

![](https://labuladong.github.io/algo/images/qrcode.jpg)

======其他语言代码======

[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);
};

```