丢棋子问题（鹰蛋问题）

丢棋子问题_牛客题霸_牛客网

问题简述

一座大楼有 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

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)

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

  鸡蛋掉落 - 力扣官方题解

思路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 层；

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