鸡蛋掉落-两枚鸡蛋 图解题解

两枚鸡蛋、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 层，道理见下方问答）。

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];
    }
}