鸡蛋掉落-两枚鸡蛋 图解题解
这道题到底在问什么
- 输入
- n = 2
- 输出
- 2
- 输入
- n = 1
- 输出
- 1
- 输入
- 本节演示 n = 10
- 输出
- 4
先想最直接的笨办法
一句话套路:枚举第一枚蛋首扔的层 j,碎了往下 j-1 层线性兜底、没碎往上是 f[i-j] 子问题,两者取坏的加一,再对所有 j 取最小。f[0]=0,答案 f[n]。（动画第 3 步）
最优解：一步一步想明白
- 3一句话套路:枚举第一枚蛋首扔的层 j,碎了往下 j-1 层线性兜底、没碎往上是 f[i-j] 子问题,两者取坏的加一,再对所有 j 取最小。f[0]=0,答案 f[n]。
- 4先把地基打好。数组第 0 格代表「0 层楼」这个边界:楼都没有,临界层只能是 0,不用扔任何一次,所以 f[0] = 0。后面每一格 f[i] 都要靠它左边已经算好的这些值往右推。
- 5轮到第 1 格。要定 f[1],就把第一枚蛋的首扔层 j 从 1 试到 1:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[1-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
- 6锁定 f[1] = 1。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[0] = 0;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 0,再加首扔这一次,合计 1。这个值填进第 1 格,继续往右推。
- 7轮到第 2 格。要定 f[2],就把第一枚蛋的首扔层 j 从 1 试到 2:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[2-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
- 8锁定 f[2] = 2。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[1] = 1;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 1,再加首扔这一次,合计 2。这个值填进第 2 格,继续往右推。
- 9轮到第 3 格。要定 f[3],就把第一枚蛋的首扔层 j 从 1 试到 3:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[3-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
- 10锁定 f[3] = 2。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[1] = 1;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 1,再加首扔这一次,合计 2。这个值填进第 3 格,继续往右推。
- 11轮到第 4 格。要定 f[4],就把第一枚蛋的首扔层 j 从 1 试到 4:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[4-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
- 12锁定 f[4] = 3。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 4 格,继续往右推。
- 13轮到第 5 格。要定 f[5],就把第一枚蛋的首扔层 j 从 1 试到 5:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[5-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
- 14锁定 f[5] = 3。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 5 格,继续往右推。
- 15轮到第 6 格。要定 f[6],就把第一枚蛋的首扔层 j 从 1 试到 6:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[6-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 3 层最省。
- 16锁定 f[6] = 3。绿色那格是首扔在第 3 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 2 层线性兜底要 2 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 6 格,继续往右推。
- 17轮到第 7 格。要定 f[7],就把第一枚蛋的首扔层 j 从 1 试到 7:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[7-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
- 18锁定 f[7] = 4。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 7 格,继续往右推。
- 19轮到第 8 格。要定 f[8],就把第一枚蛋的首扔层 j 从 1 试到 8:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[8-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
- 20锁定 f[8] = 4。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 8 格,继续往右推。
- 21轮到第 9 格。要定 f[9],就把第一枚蛋的首扔层 j 从 1 试到 9:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[9-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 3 层最省。
- 22锁定 f[9] = 4。绿色那格是首扔在第 3 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 2 层线性兜底要 2 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 9 格,继续往右推。
- 23轮到第 10 格。要定 f[10],就把第一枚蛋的首扔层 j 从 1 试到 10:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[10-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 4 层最省。
- 24锁定 f[10] = 4。绿色那格是首扔在第 4 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 3 层线性兜底要 3 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 10 格,继续往右推。
- 25整张表填满了,答案 f[10] = 4。绿色高亮的 1、3、6、10 是 f 值每上一个台阶的临界楼层,它们恰好是三角形数 1、1+2、1+2+3、1+2+3+4。含义很直白:允许扔 k 次时,第一枚蛋依次跨 k、k-1 一直到 1 层,最多能覆盖 k 加到 1 也就是 k 乘 k 加 1 除以 2 层楼。10 正好等于 4 乘 5 除以 2,所以 4 次够用,这也解释了为什么 n = 10 的答案就是 4。
⚠️ 容易写错的地方
✗ 错：蛋碎时把往下的兜底次数写成 j 层
✓ 对：碎了只需在下面 j-1 层里线性试
首扔在第 j 层,碎了说明临界层在 1 到 j-1 这 j-1 层里,兜底是 j-1 次不是 j 次;多算一层会让答案偏大
✗ 错：两个分支取小的那个 min(j-1, f[i-j])
✓ 对：要取坏的那个 max
f[i] 求的是最坏情况下的保证次数,必须按两种结果里更费的那条路算,所以是 max 不是 min
✗ 错：C++ / Java 用整型最大值当哨兵
✓ 对：用 1 左移 29 位或 memset 0x3f 这类留余量的大数
INT_MAX 再加 1 会溢出成负数,反而被 min 当成「最省」选走,把答案带偏;Python 的浮点 inf 无此问题
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int twoEggDrop(int n) {
int f[n + 1];
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i] = min(f[i], 1 + max(j - 1, f[i - j]));
}
}
return f[n];
}
};Java
import java.util.*;
class Solution {
public int twoEggDrop(int n) {
int[] f = new int[n + 1];
Arrays.fill(f, 1 << 29);
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i] = Math.min(f[i], 1 + Math.max(j - 1, f[i - j]));
}
}
return f[n];
}
}复杂度
时间
O(n²)
外层枚举楼层 i 从 1 到 n,内层枚举首扔层 j 从 1 到 i,总比较次数约 n² 的一半,是平方级
空间
O(n)
按峰值算:只用一个长度 n+1 的一维数组 f,没有开二维表,所以是线性空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 鸡蛋掉落-两枚鸡蛋 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
状态怎么定义,转移方程是什么?+
设 f[i] 为只有 i 层楼、2 枚蛋时最坏情况的最少扔数。枚举第一枚蛋首扔层 j:碎了往下 j-1 层线性兜底花 j-1 次,没碎往上是子问题 f[i-j]。转移 f[i] = min 对所有 j 取 1 + max(j-1, f[i-j]),边界 f[0]=0,答案 f[n]。时间 O(n²),空间 O(n)。
有没有比 O(n²) 更快的办法?+
有。反过来问「扔 k 次最多能测多少层」,第一枚蛋依次跨 k、k-1 直到 1 层,累计 k+(k-1)+…+1 = k(k+1)÷2 层,正是三角形数。于是答案就是最小的次数 k 满足 k(k+1)÷2 ≥ n。可以直接从小到大累加三角形数、也可以解一元二次方程,时间做到 O(√n) 甚至 O(1)。
推广到更多蛋会怎样?+
经典的 k 枚蛋、n 层楼是同一族 DP:g[k][i] = min 对首扔层 j 取 1 + max(g[k-1][j-1], g[k][i-j]),碎了少一枚蛋看下面、没碎蛋数不变看上面。两枚蛋是它 k=2 的特例,所以能进一步用三角形数化简。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 鸡蛋掉落-两枚鸡蛋 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。