给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：k = 1, n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2：
输入：k = 2, n = 6 输出：3
示例 3：
输入：k = 3, n = 14 输出：4
提示：
1 <= k <= 1001 <= n <= 104
思路：
状态定义与状态转移方程，定义状态为 dfs(i,j)，表示在有 i 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。
在 dfs(i−1,j−1)+1 楼扔第一枚鸡蛋：
如果鸡蛋碎了，接下来只需要在 [1,dfs(i−1,j−1)] 中扔鸡蛋，就可以确定 f 的值。
如果鸡蛋没碎，问题变成在有 i−1 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。这个子问题的答案 dfs(i−1,j)，加上 dfs(i−1,j−1)+1，就是原问题的答案 dfs(i,j)。
所以有
dfs(i,j)=dfs(i−1,j)+dfs(i−1,j−1)+1
递归边界：dfs(0,j)=dfs(i,0)=0。无法扔鸡蛋。
递归入口：枚举 i=1,2,3,⋯，首个满足 dfs(i,k)≥n 的 i 是答案。
dfs函数：python
@cache # 使用缓存装饰器来记忆化结果，避免重复计算
def dfs(i: int, j: int) -> int: #dfs代表 i次操作，k个鸡蛋最多能确定的楼层if i == 0 or j == 0:return 0return dfs(i - 1, j) + dfs(i - 1, j - 1) + 1 目的：dfs 函数计算使用 i 次移动和 j 个鸡蛋可以测试的最大楼层数。
基础情况：如果 i（移动次数）或 j（鸡蛋数量）为 0，则无法测试任何楼层，因此返回 0。
递归关系：
dfs(i - 1, j)：鸡蛋没有打破的情况；你少了一次移动，但鸡蛋数量相同。dfs(i - 1, j - 1)：鸡蛋打破的情况；你少了一次移动，并且少了一个鸡蛋。+ 1：代表当前的移动。
记忆化：@cache 装饰器缓存 dfs(i, j) 的结果，防止重复计算，优化递归调用。
superEggDrop函数：python
class Solution:def superEggDrop(self, k: int, n: int) -> int:for i in count(1): # 从 1 开始枚举 iif dfs(i, k) >= n:return i目的：确定使用 k 个鸡蛋测试 n 层楼所需的最少移动次数。
逻辑：
- 它从 1 开始递增地增加移动次数
i。 - 对于每个
i，它检查dfs(i, k)（使用i次移动和k个鸡蛋可以测试的最大楼层数）是否大于或等于n。 - 一旦满足这个条件，它就返回
i作为所需的最少移动次数。
理解递归关系：
在 dfs 函数中使用的递归关系：python
dfs(i, j) = dfs(i - 1, j) + dfs(i - 1, j - 1) + 1这个公式基于每次移动的两种可能性：
-
鸡蛋没有打破（安全掉落）： 你可以测试所有使用少一次移动和相同数量鸡蛋可以测试的楼层。 由
dfs(i - 1, j)表示。 -
鸡蛋打破： 你可以测试所有低于当前楼层的楼层，这些楼层可以使用少一次移动和少一个鸡蛋来测试。 由
dfs(i - 1, j - 1)表示。 -
当前楼层：
+ 1表示当前正在测试的楼层。
时间和空间复杂度分析：
-
时间复杂度：
dfs(i, j)的唯一状态总数为 O(i * j)。 由于i可以变化到所需的最少移动次数，而j是鸡蛋的数量，最坏情况下的时间复杂度可以达到 O(n * k)。 循环增加i直到dfs(i, k) >= n，对于大的n和小的k，这可能效率不高。 -
空间复杂度： 由于记忆化，空间复杂度也是 O(i * j)，用于存储每个状态在缓存中的结果。
潜在优化：
- 动态规划（迭代方法）： 与其使用递归和记忆化，不如实现一个通常由于开销较小而运行更快的迭代 DP 解决方案。
python
class Solution:def superEggDrop(self, k: int, n: int) -> int:dp = [0] * (k + 1)moves = 0while dp[k] < n:moves += 1for j in range(k, 0, -1):dp[j] = dp[j] + dp[j - 1] + 1return moves解释： dp[j] 表示使用 j 个鸡蛋和 moves 次移动可以测试的最大楼层数。 循环继续直到 dp[k] >= n，意味着我们已经找到了所需的最少移动次数。
- 二分搜索优化： 使用二分搜索找到满足
dfs(i, k) >= n的最小i。
python
class Solution:def superEggDrop(self, k: int, n: int) -> int:left, right = 1, nwhile left < right:mid = (left + right) // 2if dfs(mid, k) < n:left = mid + 1else:right = midreturn left解释： 这将每次迭代的次数减半，提高效率。 dfs 函数保持不变，但现在我们更有效地搜索 i。
- 数学解法： 利用最小移动次数可以通过二项式系数计算的事实。
python
import mathclass Solution:def superEggDrop(self, k: int, n: int) -> int:def combination(m, k):c = 0for i in range(1, k + 1):c += math.comb(m, i)if c >= n:return Truereturn Falseleft, right = 1, nwhile left < right:mid = (left + right) // 2if not combination(mid, k):left = mid + 1else:right = midreturn left解释： 这种方法计算累积的组合数，以确定是否可以在 m 次移动中使用 k 个鸡蛋测试 n 层楼。
