题目描述
思路解析
一句话答案：LeetCode 1884 鸡蛋掉落-两枚鸡蛋用一维动态规划：f[i] 记 i 层最坏最少扔几次，枚举首扔层 j，碎了往下 j-1 兜底、没碎看 f[i-j]，取最坏加一再对 j 取最小，时间 O(n²)、空间 O(n)。
两枚鸡蛋、n 层楼，到底在求哪个数
一栋 n 层楼有个临界楼层：比它高的层扔鸡蛋会碎，它或更低不碎。手里 2 枚一样的蛋，碎了报废、没碎捡回接着用。求最坏情况下最少扔几次能定位它。题面 n=2 答案 2、n=1 答案 1，本文用 n=10 演示、答案 4。
一枚蛋只能从第 1 层逐层试、最坏 n 次；两枚才敢让第一枚大步跨扔，碎了第二枚兜底。
把每种扔法都排开试，会炸成什么样
首扔哪层、碎了没碎各挪到哪，每步都分叉，把每种扔法全排开模拟，方案数随楼层指数级铺开，『还剩 8 层要定位』还会在不同开局里反复重算。
『楼高 i 层最少扔几次』答案固定，算一次存下来直接查，指数枚举就压成一张表——这就是动态规划（把每个小问题的答案算一遍存进 f 数组、后面直接取）。
f[i] 该记什么，第 0 格为什么是 0
f[i] 表示『楼高正好 i 层时最坏情况下最少扔几次能定位临界楼层』（状态定义，即讲清每格存什么量），答案是 f[n]。
第 0 格：楼高 0 层不用扔，f[0]=0，不用再往下拆的起点（base case）。之后每格靠左边已算好的值往右推。
碎与不碎取最坏，再对首扔层取最省
算 f[i] 试首扔在第 j 层（j 取 1 到 i）。碎了：临界层在下面 j-1 层里，第二枚只能一层层试，最坏 j-1 次。没碎：剩上面 i-j 层、两枚都在，是更小的同类问题 f[i-j] 次。
这一扔先花一次，结局不由你挑，最坏情况两条都得扛住、取更大，再对首扔层 j 取最省：f[i]=min(1+max(j-1, f[i-j]))，j 取 1 到 i（转移式，即由更小的格子推出当前格）。
拿 n=10 把 f[0] 到 f[10] 逐格填一遍
先摆 f[0]=0。f[1] 只能首扔第 1 层，碎了往下 0 层、没碎看 f[0]=0，取坏加一得 f[1]=1。f[2]：首扔第 1 层 1+max(0, f[1]=1)=2，首扔第 2 层 1+max(1, f[0]=0)=2，f[2]=2。f[3] 首扔第 2 层最省，f[3]=2。f[4] 首扔前三层都是 3，f[4]=3。
往右每格照样试一圈取最小：f[5]=3、f[6]=3、f[7]=4、f[8]=4、f[9]=4、f[10]=4（首扔第 4 层：没碎接 f[6]=3、碎了兜底 3 次，取坏加一得 4）。答案 4。
碎了往下写成 j 层，f[4] 为什么会算少一次
碎了兜底是 j-1 层不是 j——首扔那层已试过，只需再排查下面 j-1 层，写成 j 就重复数首扔层、代价虚高连锁整张表全偏。括号里该取 max 写成 min 是另一处反写，等于赌每次撞好结局，可题目问最坏情况。C++、Java 哨兵（哨兵=占位用的假极大值）别用 INT_MAX，加 1 溢出成负数被 min 误选。
外层 i 从 1 到 n、内层 j 从 1 到 i，约 n²/2 次比较，时间 O(n²)（大 O 记号描述规模变大时操作数怎么涨）；长 n+1 的数组 f，空间 O(n)。边界：n=0 没楼 f[0]=0，n=1 扔一次 f[1]=1，n=6 恰好 3 次（3 次最多覆盖 1+2+3=6 层，道理见下方问答）。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:枚举第一枚蛋首扔的层 j,碎了往下 j-1 层线性兜底、没碎往上是 f[i-j] 子问题,两者取坏的加一,再对所有 j 取最小。f[0]=0,答案 f[n]。
先把地基打好。数组第 0 格代表「0 层楼」这个边界:楼都没有,临界层只能是 0,不用扔任何一次,所以 f[0] = 0。后面每一格 f[i] 都要靠它左边已经算好的这些值往右推。
轮到第 1 格。要定 f[1],就把第一枚蛋的首扔层 j 从 1 试到 1:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[1-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
锁定 f[1] = 1。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[0] = 0;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 0,再加首扔这一次,合计 1。这个值填进第 1 格,继续往右推。
轮到第 2 格。要定 f[2],就把第一枚蛋的首扔层 j 从 1 试到 2:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[2-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
锁定 f[2] = 2。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[1] = 1;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 1,再加首扔这一次,合计 2。这个值填进第 2 格,继续往右推。
轮到第 3 格。要定 f[3],就把第一枚蛋的首扔层 j 从 1 试到 3:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[3-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
锁定 f[3] = 2。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[1] = 1;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 1,再加首扔这一次,合计 2。这个值填进第 3 格,继续往右推。
轮到第 4 格。要定 f[4],就把第一枚蛋的首扔层 j 从 1 试到 4:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[4-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
锁定 f[4] = 3。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 4 格,继续往右推。
轮到第 5 格。要定 f[5],就把第一枚蛋的首扔层 j 从 1 试到 5:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[5-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
锁定 f[5] = 3。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 5 格,继续往右推。
轮到第 6 格。要定 f[6],就把第一枚蛋的首扔层 j 从 1 试到 6:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[6-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 3 层最省。
锁定 f[6] = 3。绿色那格是首扔在第 3 层、蛋没碎时落到的子问题 f[3] = 2;而蛋碎时往下 2 层线性兜底要 2 次。两条路取坏的是 2,再加首扔这一次,合计 3。这个值填进第 6 格,继续往右推。
轮到第 7 格。要定 f[7],就把第一枚蛋的首扔层 j 从 1 试到 7:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[7-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 1 层最省。
锁定 f[7] = 4。绿色那格是首扔在第 1 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 0 层线性兜底要 0 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 7 格,继续往右推。
轮到第 8 格。要定 f[8],就把第一枚蛋的首扔层 j 从 1 试到 8:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[8-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 2 层最省。
锁定 f[8] = 4。绿色那格是首扔在第 2 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 1 层线性兜底要 1 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 8 格,继续往右推。
轮到第 9 格。要定 f[9],就把第一枚蛋的首扔层 j 从 1 试到 9:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[9-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 3 层最省。
锁定 f[9] = 4。绿色那格是首扔在第 3 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 2 层线性兜底要 2 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 9 格,继续往右推。
轮到第 10 格。要定 f[10],就把第一枚蛋的首扔层 j 从 1 试到 10:碎了往下 j-1 层线性兜底,没碎往上看子问题 f[10-j],两者取坏的加一。左边蓝色的格子都是已经算好的 f 值,可以直接查用。比一圈发现首扔在第 4 层最省。
锁定 f[10] = 4。绿色那格是首扔在第 4 层、蛋没碎时落到的子问题 f[6] = 3;而蛋碎时往下 3 层线性兜底要 3 次。两条路取坏的是 3,再加首扔这一次,合计 4。这个值填进第 10 格,继续往右推。
整张表填满了,答案 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。
三个边界都能手验:0 层 0 次、1 层 1 次、6 层因 6=3×4÷2 恰好 3 次。
面试三连:转移 f[i]=min(1+max(j-1,f[i-j]))、O(√n) 三角形数捷径、以及推广到 k 枚蛋的二维 DP。
参考代码
from __future__ import annotationsfrom 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]复杂度
- 时间：O(n²)，外层枚举楼层 i 从 1 到 n,内层枚举首扔层 j 从 1 到 i,总比较次数约 n² 的一半,是平方级
- 空间：O(n)，按峰值算:只用一个长度 n+1 的一维数组 f,没有开二维表,所以是线性空间
易错点
面试追问把动画讲成自己的话
追问状态怎么定义,转移方程是什么?
追问有没有比 O(n²) 更快的办法?
追问推广到更多蛋会怎样?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使二进制字符串字符交替的最少反转次数
LeetCode 1888 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题