# 丢棋子问题（鹰蛋问题）

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#动态规划) [![](https://img.shields.io/static/v1?label=\&message=%E7%BB%8F%E5%85%B8\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#经典)

> [丢棋子问题\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266)

**问题简述**

```
一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。

给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。
```

**思路1**

* 定义 `dp(k, n)` 表示 k 个棋子扔 n 层最坏情况下需要的最少次数；
* 初始化有 `dp(0, n) = dp(k, 0) = 0, dp(1, n) = n, dp(k, 1) = 1`；

  > 为什么要初始化 `k` 或 `n` 为 `0` 的情况？
* 递推公式： `dp(k, n) = 1 + min{max{dp(k-1, t-1), dp(k, n-t)}}, 1 <= t <= n`；

  > 假设在第 `t` 层扔下，有两种可能：如果碎了，则继续用 `k-1` 个蛋在 `t-1` 层楼尝试；如果没碎，则继续用 `k` 个蛋在 `n-t` 层楼尝试，取其中较大值作为最差情况，即 `max{dp(k-1, t-1), dp(k, n-t)}`；而 `t` 可以取 `[1, n]`，取其中最小值作为最少次数；`+1` 表示当前层扔了 1 次；
  >
  > > [复工复产找工作？先来看看这道面试题：双蛋问题\_哔哩哔哩\_bilibili](https://www.bilibili.com/video/BV1KE41137PK?t=600.0)

<details>

<summary><strong>Python（超时）</strong></summary>

```python
class Solution:
    def solve(self, n: int, k: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(k, n):  # k 个棋子扔 n 层最坏情况下需要的最少次数
            if k == 0 or n == 0: return 0
            if k == 1 or n == 1: return n
            return 1 + min(max(dp(k - 1, t - 1), dp(k, n - t)) for t in range(1, n + 1))

        return dp(k, n)
```

</details>

* 直接使用上述方法会超时，可以利用**二分**或**决策单调性**（四边形法则）优化复杂度：

  > [鸡蛋掉落 - 力扣官方题解](https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2/)

**思路2：反向思维（推荐）**

* 定义 `dp(i, j)` 表示 i 个棋子扔 j 次最多能确定的层数；

  > 类似 01 背包 的两种尝试方法：1）固定重量需要的最小空间，2）固定空间能放的最大重量
* 初始化 `dp(0, j) = dp(i, 0) = 0, dp(1, j) = j, dp(i, 1) = 1`；
* 递推公式：`dp(i, j) = 1 + dp(i - 1, j - 1) + dp(i, j - 1)`；

  > 如果棋子碎了，对应 `r1 := dp(i-1,j-1)`，说明这一层的**下方**可以有 `r1` 层；\
  > 如果棋子没碎，对应 `r2 := dp(i,j-1)`，说明这一层的**上方**可以有 `r2` 层；\
  > `+1` 表示当前回合确定了 1 层；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def solve(self , n: int, k: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(i, j):  # i 个棋子扔 j 次最多能确定的层数
            if i == 0 or j == 0: return 0
            if i == 1 or j == 1: return j
            return 1 + dp(i - 1, j - 1) + dp(i, j - 1)
            
        c = 0
        while dp(k, c) < n:
            c += 1
            
        return c
```

</details>
