What is the main strategy for Egg Drop With 2 Eggs and N Floors?

Use state transition dynamic programming to select floors that balance remaining attempts, reducing maximum drops.

Can we apply binary search directly with 2 eggs?

No, binary search can fail in worst case because breaking the first egg too early increases total drops.

How does triangular number optimization help?

It ensures each drop reduces remaining potential floors optimally, achieving minimal worst-case attempts.

What is the time complexity for this problem?

Naive DP is O(n^2), but using the triangular number approach reduces it to O(n).

Does GhostInterview show step-by-step drops for n floors?

Yes, it calculates each floor to drop from and tracks outcomes to explain the minimal moves strategy.

#1884

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

鸡蛋掉落-两枚鸡蛋

给你 2 枚相同的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会碎。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 ）。如果鸡蛋…

数学动态规划

题目描述

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：

输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

提示：

1 <= n <= 1000

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示有两枚鸡蛋，在 $i$ 层楼中确定 $f$ 的最小操作次数。初始时 $f[0] = 0$ ，其余 $f[i] = +\infty$ 。答案为 $f[n]$ 。

考虑 $f[i]$ ，我们可以枚举第一枚鸡蛋从第 $j$ 层楼扔下，其中 $1 \leq j \leq i$ ，此时有两种情况：

鸡蛋碎了，此时我们剩余一枚鸡蛋，需要在 $j - 1$ 层楼中确定 $f$ ，这需要 $j - 1$ 次操作，因此总操作次数为 $1 + (j - 1)$ ；
鸡蛋没碎，此时我们剩余两枚鸡蛋，需要在 $i - j$ 层楼中确定 $f$ ，这需要 $f[i - j]$ 次操作，因此总操作次数为 $1 + f[i - j]$ 。

综上，我们可以得到状态转移方程：

f[i] = \min_{1 \leq j \leq i} \{1 + \max(j - 1, f[i - j])\}

最后，我们返回 $f[n]$ 即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为楼层数。

1

2

3

4

5

6

7

8

class Solution:
    def twoEggDrop(self, n: int) -> int:
        f = [0] + [inf] * n
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                f[i] = min(f[i], 1 + max(j - 1, f[i - j]))
        return f[n]

speed

复杂度分析

指标	值
时间	complexity is O(n^2) for naive DP but can be optimized to O(n) using triangular number method. Space complexity is O(n) when storing only current egg states instead of full DP table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks if dropping from the middle floor is always optimal for two eggs.
question_mark
Mentions worst-case scenario and minimizing maximum drops.
question_mark
Checks understanding of state transition DP and triangular number optimization.

warning

常见陷阱

外企场景

error
Assuming binary search works with only 2 eggs, which can exceed allowed drops.
error
Failing to balance drops properly, leading to suboptimal worst-case attempts.
error
Overcomplicating DP by storing unnecessary states instead of optimizing transitions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Egg Drop with k eggs and n floors using full DP table.
arrow_right_alt
Determine minimum drops with 2 eggs and specific floor constraints.
arrow_right_alt
Compute drops when eggs have a probability of breaking instead of deterministic behavior.

help

常见问题

外企场景

继续练习

#1872 石子游戏 VIII #1896 反转表达式值的最少操作次数 #1866 恰有 K 根木棍可以看到的排列数目