鸡蛋掉落（Egg Dropping）问题的最小尝试次数

题目描述
你手上有 k 枚相同的鸡蛋，并面临一栋从第 1 层到第 n 层的高楼。已知存在一个临界楼层 f（0 ≤ f ≤ n），其中：

• 从任何低于或等于 f 的楼层扔下鸡蛋，鸡蛋不会碎（≥ f 层不碎）；
• 从任何高于 f 的楼层扔下鸡蛋，鸡蛋会碎（> f 层碎）。

你每次操作可以选择一层楼扔下一枚鸡蛋，然后观察鸡蛋是否破碎。目标是在最坏情况下，用最少的尝试次数确定出临界楼层 f。
请你设计算法计算最坏情况下的最小尝试次数。

输入：k 个鸡蛋，n 层楼。
输出：最少尝试次数。

例子：

• 如果 k = 1，n = 5，你只有 1 枚鸡蛋，只能从第 1 层开始逐层往上试，最坏情况下需要 5 次（从 1 楼到 5 楼各扔一次）。
• 如果 k = 2，n = 5，你可以用更巧的策略减少次数，结果是 3 次（下文详述）。

解题思路详解

这是一个经典的动态规划问题，其核心在于如何利用鸡蛋的数量和剩余楼层数规划扔鸡蛋的决策，以最小化最坏情况的尝试次数。

第一步：问题定义与状态设计

我们定义状态：

dp[i][j] 表示有 i 枚鸡蛋，面对 j 层楼时，确定临界楼层所需的最少尝试次数（最坏情况下）。

我们要的最终答案是 dp[k][n]。

第二步：基础情况

考虑两种基础情况：

1. 鸡蛋数 k = 1：只有 1 枚鸡蛋，不能冒险，只能从 1 楼开始逐层往上试，最坏情况需要试完所有楼层，所以：

   dp[1][j] = j  （j ≥ 1）
   

2. 楼层数 n = 0 或 1：
   • 如果 n = 0，不需要尝试，dp[i][0] = 0。
   • 如果 n = 1，只需试一次就知道结果，dp[i][1] = 1（i ≥ 1）。

第三步：状态转移方程

假设我们当前有 i 枚鸡蛋，面对 j 层楼，我们第一次从第 x 层（1 ≤ x ≤ j）扔鸡蛋。这时有两种可能结果：

1. 鸡蛋碎了：说明临界楼层低于 x，且我们损失了一枚鸡蛋，剩下 i-1 枚鸡蛋，需要检查 x-1 层楼（因为第 1 层到第 x-1 层）。次数 = 1 + dp[i-1][x-1]。

2. 鸡蛋没碎：说明临界楼层在 x 层及以上（包括 x 层以上），剩下 i 枚鸡蛋，需要检查 j - x 层楼（因为第 x+1 层到第 j 层）。次数 = 1 + dp[i][j-x]。

由于我们考虑最坏情况，要取上面两种可能中的较大值，以保证无论实际临界楼层在哪，我们的尝试次数都能覆盖：

最坏尝试次数 = 1 + max(dp[i-1][x-1], dp[i][j-x])

我们要选择最优的 x 来最小化这个最坏尝试次数，所以：

dp[i][j] = min_{x=1..j} { 1 + max(dp[i-1][x-1], dp[i][j-x]) }

第四步：举例推算

以 k = 2, n = 5 为例，我们手工推算 dp[2][5]。

先初始化：

• dp[1][j] = j 对所有 j。
• dp[i][0] = 0，dp[i][1] = 1。

计算 dp[2][1]：只有 1 层楼，只需 1 次。
计算 dp[2][2]：对 x = 1 或 2 尝试，选最小值。

• 若 x = 1：碎了→剩 1 蛋 0 层（0 次）+1 = 1；没碎→剩 2 蛋 1 层（1 次）+1 = 2，最坏=2。
• 若 x = 2：碎了→剩 1 蛋 1 层（1 次）+1=2；没碎→剩 2 蛋 0 层（0 次）+1=1，最坏=2。
  所以 dp[2][2] = 2。

计算 dp[2][3]：

• x = 1：max(dp[1][0]=0, dp[2][2]=2) = 2 → 3
• x = 2：max(dp[1][1]=1, dp[2][1]=1) = 1 → 2
• x = 3：max(dp[1][2]=2, dp[2][0]=0) = 2 → 3
  最小是 2，所以 dp[2][3] = 2。

计算 dp[2][4]：

• x = 1：max(0, dp[2][3]=2) = 2 → 3
• x = 2：max(1, dp[2][2]=2) = 2 → 3
• x = 3：max(2, dp[2][1]=1) = 2 → 3
• x = 4：max(3, 0) = 3 → 4
  最小是 3，所以 dp[2][4] = 3。

计算 dp[2][5]：

• x = 1：max(0, dp[2][4]=3) = 3 → 4
• x = 2：max(1, dp[2][3]=2) = 2 → 3
• x = 3：max(2, dp[2][2]=2) = 2 → 3
• x = 4：max(3, dp[2][1]=1) = 3 → 4
• x = 5：max(4, 0) = 4 → 5
  最小是 3，所以 dp[2][5] = 3。

结果：最少尝试次数是 3。

第五步：算法实现

直接按上述递推计算，三层循环（i, j, x），复杂度 O(k * n²)。这在 n 较大时会很慢，但可以用于理解思路。

优化：注意到在固定 i, j 时，dp[i-1][x-1] 随 x 增大而增大，dp[i][j-x] 随 x 增大而减小，最优的 x 是这两个函数交点附近，可以用二分搜索找 x 来将内层循环降为 O(log n)。但此处我们先给出基本解法。

伪代码：

function eggDrop(k, n):
   dp[1..k][0..n] 初始化为大数
   for i = 1 to k:
      dp[i][0] = 0
      dp[i][1] = 1
   for j = 1 to n:
      dp[1][j] = j
   for i = 2 to k:
      for j = 2 to n:
         dp[i][j] = INF
         for x = 1 to j:
            broken = dp[i-1][x-1]
            not_broken = dp[i][j-x]
            worst = 1 + max(broken, not_broken)
            if worst < dp[i][j]:
               dp[i][j] = worst
   return dp[k][n]

第六步：理解动态规划表的意义

动态规划表的每个状态记录了在当前鸡蛋数和楼层数下的最优策略的最坏尝试次数。通过尝试所有可能的第一次扔的楼层 x，我们能在鸡蛋碎了和没碎的两种最坏可能性之间取得平衡，从而让最坏情况下的尝试次数尽量小。

最终答案：当输入 k 和 n 时，程序返回 dp[k][n] 即为最小尝试次数。