题目描述
思路解析动画文字版
一句话套路:枚举第一枚蛋首扔的层 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题