01

60 秒回答模板

经典 DP 定义可以是 dp[k][n] 表示 k 个鸡蛋、n 层楼在最坏情况下确定临界楼层所需的最少次数。若第一次在 x 层扔，碎了要在 x-1 层里用 k-1 个鸡蛋查；没碎要在 n-x 层里仍用 k 个鸡蛋查，因此代价是 1 + max(dp[k-1][x-1], dp[k][n-x])，对 x 取最小。也可以用更高效的反向 DP：moves 次、k 个鸡蛋最多能覆盖 dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1 层。面试要求讲 DP 解法时，先讲状态和最坏情况，再补优化。

考点 最坏情况
难度 真实面经题
回答目标 讲清方法、边界和追问
02

深入解析

01

明确最坏情况

题目不是求平均次数，而是在任何临界楼层下都能确定答案的最少测试次数。因此一次选择要考虑碎和不碎中更差的一边，这也是 DP 转移里取最大值的原因。

02

楼层维度 DP

dp[k][n] 表示 k 个鸡蛋和 n 层楼的最少最坏次数。枚举第一次扔的楼层 x，用碎和不碎两个子问题转移，并把子问题规模严格缩小。

03

转移里的 max 和 min

固定 x 后，面试官可能选择更坏结果，所以用 max；我们可以选择最优 x，所以对所有 x 取 min。这正是博弈式最坏情况 DP。

04

覆盖楼层优化

另一种状态是 dp[m][k] 表示 m 次测试、k 个鸡蛋最多能覆盖多少层。一次测试把碎、不碎和当前层三部分合起来，转移更简洁。

05

边界和复杂度

一个鸡蛋时只能线性试，零层楼需要零次。朴素 DP 枚举楼层较慢，覆盖楼层 DP 通常更适合面试中说明优化方向，也更容易扩展到大楼层数。

03

易错点

  • 不要把平均次数当成最坏次数。
  • 不要忘记鸡蛋碎后鸡蛋数量减少，不碎时鸡蛋数量不变。
  • 不要只给递归暴力，要说明状态复用和边界条件。
04

面试官追问

为什么转移里要取 max？

因为要保证无论鸡蛋碎不碎都能确定答案，最坏情况由更难的一侧决定。

为什么外层又要取 min？

测试楼层 x 是我们的策略选择，要从所有可能策略中选最小最坏代价。

覆盖楼层 DP 的公式怎么理解？

一次测试后，碎了覆盖下面 dp[m-1][k-1] 层，不碎覆盖上面 dp[m-1][k] 层，再加当前测试层。