高楼扔鸡蛋这题我最早是在面试前刷题时撞见的,当时第一反应是二分:100 层楼,最多 7 次搞定。结果被一句你只有两个鸡蛋直接问懵——最坏情况下第一次在 50 层摔碎,第二个蛋就得从 1 层一路爬上去,总共 50 次,比老老实实顺序试还难看。这道经典烧脑算法逻辑题真正的考点从来不是会不会二分,而是在失败预算有限的前提下,怎么做最坏情况下的最优搜索。下面我把题面定义、状态设计、递推推导、代码实现、参数验证,再到工程里的同构场景完整拆一遍,踩过的坑都标出来,方便你直接抄作业。1. 题面里的三个隐藏开关:临界点、最坏情况、蛋够不够1.1 临界点究竟是一个楼层,还是一个区间先把定义钉死,否则后面所有数字都会飘。设存在一个最高安全层T:鸡蛋从第 1 层到第 T 层扔下去都不碎,从第 T1 层开始扔下去必碎。T 的取值范围是 0 到 N,共 N1 种可能——T0 表示一层都摔得碎,不要把它当成不存在的边界。这就是这道题里最容易被忽略的一个结果集合。为什么这件事重要?因为你要求的是测出临界点,而测出意味着要把 N1 种可能压缩到只剩 1 种。多数人的直觉里只有第 1 到第 N 层,结果集合被悄悄记成了 N 个,边界数字上就会差出一次。100 层、2 个蛋的情况下,两种约定都算 14 次,所以这个坑平时不显形;一旦换成 1 个蛋 100 层,答案立刻分成 100 次和 99 次两个版本。写代码之前先确认题目保证的是什么,这一步省不掉。1.2 最少次数默认是最坏情况,不是期望面试和竞赛里问最少几次,标准的语义是:不管断点落在哪一层,你都能给出确定答案所需要的最小次数上界。它对应的是一个 min-max 结构,等价于有一个对手在每一步都替你挑更糟糕的那一支结果。这就是为什么递推式里出现的是 max 而不是加权的平均值,也是很多人第一反应用期望去算然后发现自己算了个寂寞的原因。如果题目改成平均需要几次,那又是另一道题了:最优策略会变得激进,倾向于先在高楼层试探以尽早收敛,代价是最坏情况下可能非常难看。这两种目标函数不能混用,先把目标函数读清楚再动笔。1.3 鸡蛋数量是预算,不是参数碎掉的蛋不能复用,所以鸡蛋数 K 的本质是你能承受多少次失败。K 取两个极端时题目会退化成两个熟悉的东西:K1 时,你只有一次失败机会,只能从 1 层开始一层一层往上试,退化成线性扫描;K 大到一定程度(具体是ceil(log2(N1))),失败预算足够支撑每一步对半砍,退化成标准的二分查找。有意思的恰恰是中间那段:K 从 2 到 7,每加一个蛋带来的收益都在衰减。这道题的烧脑就烧在这里——它不是一个套模板就能秒杀的问题,而是一个需要自己定义状态、自己推导平衡关系的搜索问题。2. 为什么二分查找在这里会翻车2.1 二分的隐含前提是失败可以无限重来二分查找能在 7 次内定位 100 层里的断点,靠的是每一步把候选区间砍半。但这个操作的隐藏前提是:摔碎一颗蛋之后,你还能继续在剩下的区间里摔。逻辑上它要求蛋的供应是无限的,或者至少要log2(N1)颗。两个蛋只允许你碎两次,第二次碎完你就只能靠已有信息硬猜了,而硬猜在要求确定性的题目里是不算数的。换句话说,二分不是更优策略,在这道题里它是根本用不了的策略。这跟很多工程直觉是冲突的——我们平时习惯了查找就用二分,所以第一次碰到这题的人大概率会答 7。2.2 算一下二分 两个蛋的最坏情况假设硬上二分。第一次在 50 层扔:碎了:剩 1 个蛋,断点落在 1 到 49 层,只能从 1 层开始逐层往上爬,最坏 49 次。总计 1 49 50 次。没碎:第二次在 75 层扔。如果这次碎了,断点落在 51 到 74 层,共 24 层,线性扫描最坏 24 次,总计 2 24 26 次。如果还没碎,继续 88 层、94 层……越往后区间越窄,但线性扫描的尾巴始终存在。最坏情况 50 次。这个数字甚至比不二分、直接从 1 层往上试的 100 次好不了多少,还多搭进去一颗蛋。2.3 等差步长的朴素改进:10、20、30 为什么还是不够好稍微动点脑子会想到:第一颗蛋别对半砍,改成每 10 层扔一次,10、20、30……100。这样最坏情况是:第一颗蛋扔到第 10 次(100 层)才碎,此时区间是 91 到 100 层,第二颗蛋线性扫描 9 次,总共 19 次。比 50 好太多了。但它还不是最优,原因是步长选得不讲道理。第一颗蛋往上走的过程中,每多用一次,留给第二颗蛋的楼层数就越多,而第二颗蛋能用的次数 总次数 - 第一颗蛋已用次数。固定步长 10 意味着这两个量没有被打平:第一颗蛋用得少的时候(早碎),第二颗蛋有富余;第一颗蛋用得多的时候(晚碎),第二颗蛋就吃紧。理想状态应该是第一颗蛋每多扔一次,步长就减 1,让已用次数 待用次数恒定。这正好导出 14 这个数字。3. 把状态量换成摔几次、还剩几个蛋:g(m,k) 的三项递推3.1 正向状态 f(i,j) 和它的两支分叉最直观的建模是正向的:令f(i, j)表示还有 i 层楼待查、手里有 j 个蛋时,最坏情况下的最少投掷次数。第一次从这 i 层里的第 x 层扔(段内相对编号),有两条分支:碎了:断点在 x 以下,剩余待查 x-1 层,蛋少一个 →f(x-1, j-1)没碎:断点在 x 以上,剩余待查 i-x 层,蛋数不变 →f(i-x, j)对手会挑更坏的那一支,所以这次的代价是1 max(f(x-1, j-1), f(i-x, j)),而我们的决策是选一个让这个值最小的 x:f(i, j) min over x in [1..i] of 1 max( f(x-1, j-1), f(i-x, j) ) 边界: f(0, j) 0 f(i, 1) i这套写法最大的优点是可以反向回溯出每一步的实际投掷楼层,最大的缺点是内层要枚举 x,朴素实现是 O(K·N²)。3.2 反向状态 g(m,k):把能不能覆盖当成能力值换个方向想会舒服很多。定义g(m, k):投掷 m 次、手里有 k 个蛋,最多能覆盖多少层楼。第一颗蛋扔下去之后,局面被切成三块:中间那一层本身:这次投掷确定了它是不是断点,贡献 1它下面那段:蛋少一个,但还能再扔 m-1 次,贡献g(m-1, k-1)它上面那段:蛋数不变,还能再扔 m-1 次,贡献g(m-1, k)于是:g(m, k) g(m-1, k-1) 1 g(m-1, k) 边界: g(0, k) 0 g(m, 0) 0答案就是最小的 m 使得g(m, K) N。这个方向的好处是不用枚举决策点,直接迭代就行,复杂度 O(K·m)。先算能力再做事的思路,在资源受限的最优搜索这一类问题里几乎万能。3.3 这个递推其实是个二项式求和把g(m, k) Σ_{i1..k} C(m, i)代进去验一下,用帕斯卡恒等式C(m,i) C(m-1,i) C(m-1,i-1):g(m-1,k) g(m-1,k-1) 1 Σ_{i1..k} C(m-1,i) Σ_{i1..k-1} C(m-1,i) C(m-1,0) Σ_{i1..k} [C(m-1,i) C(m-1,i-1)] Σ_{i1..k} C(m,i)成立。几个特例值得记住:k1 时g(m,1) m,与一个蛋只能一层一层试完全吻合;k ≥ m 时g(m,k) 2^m - 1,这就是二分查找的能力上限。所以蛋再多也就那么回事,有效蛋数上限是ceil(log2(N1))。4. 从递推式到可执行的投掷表:14、27、39 是怎么来的4.1 先定总次数,再反过来定楼层100 层、2 个蛋,代入二项式形式:K2 时g(m,2) m m(m-1)/2。试 m13 得 13 78 91,不够 100;m14 得 14 91 105,够了。所以答案是 14 次。注意这里的思路顺序:先确定总共允许摔 14 次这个预算,再去安排第一次落点。第一次该从哪扔?要让即使立刻碎掉,剩下的 13 次也刚好够用。碎掉之后只剩 1 个蛋,13 次能线性覆盖 13 层,再算上这次投掷本身确定的那一层,第一次落点就是第 14 层。这个倒着算的动作是理解整道题的钥匙。4.2 步长递减的本质是次数守恒第二次落点同理:假设第一次没碎,现在还有 2 个蛋、13 次机会、待查区间是 15 到 100 层。这颗蛋在区间内最多还能往上跨 12 层,所以第二次落在 14 13 27 层。往下依次类推,步长每轮减 1:投掷序号楼层剩余次数(含本次)本次步长1141414227131333912124501111560101066999777888847799066109555119944121003封顶(理论落点 102 已越界)累加 1413…3 102,刚好盖住 100 层,还富余 2 层,所以最后一步封顶在 100。第一颗蛋每扔一次,后面步长就减 1这条规则,保证了最坏情况下第一颗蛋用完的时刻和第二颗蛋用完的时刻同时到达,这就是 14 次能够成立的全部秘密。4.3 K2 的闭式解,以及量级上的直觉把m m(m-1)/2 N整理一下得到m² m 2N,所以m ceil( ( sqrt(8N 1) - 1 ) / 2 )代入几个值:N36 时,m8(验证:8 28 36,刚好卡满);N100 时,m14;N10 亿时,m 大约是 44721。也就是说楼层数翻了 1000 万倍,次数只从 14 涨到 4 万多,这是平方根级别的增长。这个量级感受很重要:它说明在失败预算被死死限制在 2 次的情况下,单次探测的跨越能力其实衰减得非常慢。顺带提醒一个实际写代码时容易中的招:大 N 下用double开方再向上取整,有可能因为浮点误差算出 13.999999 然后 ceil 成 14、或者本该 14 却算成 13 这类结果。稳妥做法是整数二分找 m,或者算出候选值后再用g真正验一遍。5. 正向 DP 的写法与决策点单调性优化5.1 朴素 f(i,j) 在 N 大时直接卡死f(i, j)的朴素实现要对每个 i 枚举所有 x,复杂度 O(K·N²)。N100 时这根本不算事(一百万次以内的操作),但 N 到 10⁴ 就是十亿量级,基本等着超时。所以如果面试官追问楼层数很大怎么办,你得能说出优化点在哪。5.2 决策点单调,内层枚举可以换成二分固定 j 和 i,把两个分支看成关于 x 的函数:A(x) f(x-1, j-1)随 x 单调不减(下面楼层越多,最坏情况只会更差);B(x) f(i-x, j)随 x 单调不增(上面楼层越少,最坏情况只会更好)。我们最小化的是1 max(A, B)。一条单调上升的曲线和一条单调下降的曲线,它们的 max 的最小值必然出现在交点附近。于是可以用二分找第一个满足A(x) B(x)的 x,然后比较它和它左边一个位置取优即可。复杂度从 O(N) 降到 O(log N),整体变成 O(K·N·log N)。这一步的直觉是:往上多走一层,下面变难、上面变易,两个方向恰好对冲,所以最优决策点在中间某处且随 i 单调移动。5.3 反向递推的代码更短,而且自带滚动数组日常做题或者面试白板,我更推荐先写出g版本,代码短、不容易错,还能直接回答数值:def min_drops(N, K): N 层楼、K 个蛋,返回最坏情况下的最少投掷次数。 if N 0: return 0 # 蛋再多也不会比二分更快,截断掉无意义的计算 cap (N 1).bit_length() K min(K, cap) prev [0] * (K 1) # g(m-1, k) m 0 while prev[K] N: m 1 cur [0] * (K 1) for k in range(1, K 1): cur[k] prev[k] prev[k - 1] 1 prev cur return m print(min_drops(100, 2)) # 14 print(min_drops(100, 3)) # 9 print(min_drops(100, 7)) # 7 print(min_drops(36, 2)) # 8滚动数组把空间压到 O(K),时间 O(K·m),而 m 在最坏情况(K1)下就是 N,所以整体不会超过 O(K·N)。写的时候注意prev[k-1]用的是上一轮的 g 值而不是本轮已经更新过的,顺序千万别写反。5.4 要输出具体投掷方案,还是得回到正向 DPg只告诉你最少几次,不告诉你哪层扔。要复现完整策略就得建正向表,再顺着决策点回溯:def build_f(N, K): K min(K, (N 1).bit_length()) f [[0] * (K 1) for _ in range(N 1)] for i in range(1, N 1): f[i][1] i # 一个蛋只能线性扫 for j in range(2, K 1): f[1][j] 1 for i in range(2, N 1): lo, hi, best 1, i, 10 ** 9 while lo hi: mid (lo hi) // 2 cost 1 max(f[mid - 1][j - 1], f[i - mid][j]) best min(best, cost) if f[mid - 1][j - 1] f[i - mid][j]: lo mid 1 # 最优决策点还在右边 else: hi mid - 1 f[i][j] best return f def show(N, K): f build_f(N, K) eggs min(K, (N 1).bit_length()) def walk(lo, hi, e, depth): n hi - lo 1 if n 0: return if e 1 or n 1: print( * depth f逐层试 {lo}..{hi}) return best, pick 10 ** 9, 1 for x in range(1, n 1): cost 1 max(f[x - 1][e - 1], f[n - x][e]) if cost best: best, pick cost, x floor lo pick - 1 print( * depth f在 {floor} 层扔(区间 [{lo},{hi}],剩 {e} 个蛋)) walk(lo, floor - 1, e - 1, depth 1) # 碎了往下去 walk(floor 1, hi, e, depth 1) # 没碎往上去 walk(1, N, eggs, 0) show(100, 2)跑出来第一条就是在 14 层扔,接着是 27、39……和手推的表对得上。5.5 同一个逻辑的 C 版本比赛或者笔试环境里写 C 的话,核心循环几乎一一对应:#include bits/stdc.h using namespace std; int main() { int N 100, K 2; K min(K, (int)__lg(N 1) 1); // 有效蛋数截断 vectorvectorint f(N 1, vectorint(K 1, 0)); for (int i 1; i N; i) f[i][1] i; for (int j 2; j K; j) { f[1][j] 1; for (int i 2; i N; i) { int lo 1, hi i, best INT_MAX; while (lo hi) { int mid (lo hi) 1; int cost 1 max(f[mid - 1][j - 1], f[i - mid][j]); best min(best, cost); if (f[mid - 1][j - 1] f[i - mid][j]) lo mid 1; else hi mid - 1; } f[i][j] best; } } cout f[N][K] endl; // 14 }几个容易翻车的细节:f[0][j]必须初始化成 0,代表没有待查楼层;K1要单独把整列铺成 i;K 截断之后如果 K 变成 0,直接返回;如果题目要求输出方案,别忘了f[i][j]只在i-1层以上才有意义,回溯时区间长度到 0 就要停。6. 换参数验证:3 蛋 100 层为什么是 9 次6.1 一张表看清蛋数带来的收益衰减用g(m,k) Σ C(m,i)挨个试,100 层楼在不同蛋数下的答案:鸡蛋数 K最少次数验证过程1100g(m,1) m,需 m ≥ 10021414 91 105 ≥ 100;13 78 91 100399 36 84 129 ≥ 100;8 28 56 92 100488 28 56 70 162 ≥ 100577 21 35 35 21 119 ≥ 1006 及 77与二分查找的 ceil(log2(101)) 7 一致这张表的信息量比单独记住14大得多。从 1 个蛋到 2 个蛋,次数从 100 直接砸到 14,收益是数量级的;从 3 个蛋到 4 个蛋只省 1 次;到 7 个蛋就彻底撞上二分的下界,再加蛋毫无意义。边际收益递减得非常快,拐点出现在 K ≈ log2(N) 附近,这跟很多资源分配问题的曲线形状是一致的。6.2 36 层 2 个蛋恰好 8 次,是个很好的验算点g(8,2) 8 28 36,不多不少。所以 36 层是8 次能处理的上限,37 层就得 9 次。这个数字我经常拿来自查:如果代码跑出来 36 层是 7 次或者 9 次,说明二项式的求和项或者循环边界写错了。顺便说一句,很多人凭感觉认为36 层比 100 层应该省很多吧,一算只省 6 次——平方根增长的直观感受就是反直觉。6.3 蛋数上限截断:不截断就是白算前面提过k m时g(m,k) 2^m - 1,与 k 无关。所以有效蛋数是min(K, ceil(log2(N1)))。如果你没截断,而输入是100 层楼、10000 个蛋,DP 表会白白多开 9900 列,内存和时间全浪费在重复计算同一组已经饱和的值上。这是我在实际做题时踩过的一次坑:本地小样例跑得飞快,换个大 K 的参数直接内存爆掉,查了半天才发现问题不在算法本身,而在没有做能力饱和的剪枝。6.4 结果集合是 N 还是 N1:一个差一次的经典坑如果题目把最高安全层限定在 1 到 N 之间(也就是保证一定有某一层会碎),结果集合是 N 个;如果允许一层都不碎这种情形,结果集合是 N1 个。前者对应g(m,K) N,后者对应g(m,K) N1吗?不完全对——两者相差的是你需不需要额外区分一次边界情况。最干净的验证方式是拿 K1 试:允许一层都不碎时,1 个蛋 100 层要扔 100 次(从 1 层试到 100 层,全没碎则结果是 100);如果题目保证一定会在 1 到 100 层之间碎,只需试到 99 层,最坏 99 次。写代码前把答案集合的基数数清楚,再动手写循环边界,比写完之后对着 100 和 99 反复调参高效得多。7. 这类限次最坏情况搜索在工程里的映射7.1 换掉鸡蛋和楼层,结构完全一样把蛋换成高成本探测的可失败次数,把楼层换成待定位的候选集合,这道题就变成了一个通用模型:每次探测只有两种结果,其中一种结果会消耗不可再生的资源,目标是在资源耗尽之前锁定答案。举个离得比较近的场景:某个 bug 是在某次提交之后引入的,你要在一长串提交里定位它,而每次验证都要跑一遍耗时两小时的全量回归,并且团队规定最多只能浪费几次验证机会(比如线上灰度批次有限)。这时候直接上对半砍看起来很美,但如果前两次都命中有问题那一半,剩下的候选区间就只能线性扫,总耗时会炸。更稳的做法恰恰是这道题里的等差步长:一开始跨得大一些,随着消耗次数增加逐步收窄,保证最坏情况下的总代价被压平。这个思路在容量规划、限次重试的探测策略里都能直接照搬。7.2 常见翻车点清单把上面所有讨论收成一张表,写代码或面试答题前扫一眼:翻车点表现正确做法把 max 写成 min 或平均值算出 10 次左右的漂亮答案目标是保证次数,分支必须取 max忽略没碎分支蛋数不减递推里两处都写 j-1碎了 j-1,没碎仍是 j结果集合基数搞错边界值差 1 次先确认是否允许一层都不碎有效蛋数不截断大 K 时内存爆掉截到 ceil(log2(N1))K1 未单独处理数组越界或答案偏小单独把 f[i][1] 铺成 i大 N 用 double 开方偶尔少 1 次整数二分或算完用 g 验一遍只算数值不回回溯说得出 14,画不出投掷序列用正向 DP 记决策点7.3 面试现场怎么答才稳我自己的答题顺序是:先把 T 的定义和结果集合说清楚,再写出f(i,j) 1 min max(...),主动指出内层枚举可以靠决策点单调性降到 O(log N);然后补一句其实反向定义 g(m,k) 更好写,递推只有三项g(m-1,k-1) 1 g(m-1,k),把代码收敛到 O(K·m);最后报出 14,顺手画一遍 14、27、39、50、60、69、77、84、90、95、99、100 这条投掷序列。整个过程里最有说服力的是那三步:定义清楚、递推写对、数值能自洽。后来我养成了一个习惯:凡是看到最少次数保证测出临界点这几个词凑在一起,先把g(m,k) g(m-1,k-1) g(m-1,k) 1这一行写下来,再回头去套题面。这行式子只有三项,但它把次数守恒这件事一次说透了,比死记 14 这个数字有用得多。至于那个最容易忽略的g(0,k) 0,每次我都会在草稿纸边上单独写一遍,提醒自己边界条件永远比递推主体更容易写错。
到O(log n)的优化之路)
