实验四的动态规划部分鸡蛋掉落问题几乎是每个学期都要出来刷一遍存在感的题目。第一次拿到题面的人十个里有八个会下意识写二分——n 层楼鸡蛋碎了就往低处找没碎就往高处找log n 次不就搞定了然后就翻车了因为鸡蛋是消耗品碎掉的鸡蛋不会自己长回来这个不可逆的代价直接破坏了二分的适用前提。这道题真正考的不是你能不能默写出一个状态转移方程而是你能不能看穿最坏情况最小化这个目标函数以及愿不愿意把状态定义反过来写。我把这道题从实验报告一路推到面试和在线判题的场景里踩过的坑大概能列满一页纸状态定义反了、边界漏了、INF 加一溢出了、k 和 n 的输入顺序读反了、记忆化搜索爆栈了。所以这篇内容不打算只给一份能过样例的代码而是把三种解法正向 DP、反向 DP、二分优化的推导过程、复杂度账、手算验证的表、以及实验报告里最容易丢分的细节一次讲透。适合正在做算法设计与分析实验的同学也适合想重新梳理一遍动态规划状态设计思路的人——哪怕你之前完全没接触过鸡蛋掉落问题跟着往下读也能自己推出来。1. 二分查找在这道题上翻车的真实原因1.1 题意里藏着三个必须抠死的约束很多人做错这道题不是败在算法上而是败在读题上。题面通常是这样描述的有 k 个一模一样的鸡蛋一栋 n 层的楼存在一个临界楼层 F满足从第 1 层到第 F 层扔鸡蛋都不会碎从第 F1 层到第 n 层扔都会碎。注意 F 可以等于 0一楼就碎也可以等于 nn 楼都不碎。你的任务是确定 F 的值求最坏情况下最少的扔鸡蛋次数。这里面有三个约束必须一个一个抠清楚。第一鸡蛋碎了就没了没碎可以从地上捡起来接着用这一点决定了两条分支的可用资源是不对称的。第二确定 F 的值意味着你必须能唯一地锁定 F而不是猜个大概所以信息量必须足够。第三最坏情况下最少是一个 min-max 结构——你要设计一套策略让所有可能的 F 里最费劲的那一种尽可能省事。这三条里任意一条理解偏了代码就会全盘走歪。我见过最常见的误读是把最坏情况理解成平均情况于是算出来一个看似更小的数然后对着样例反复检查逻辑越查越自信。还有一种是没意识到 F 可以从 0 开始导致边界条件少讨论了一档。1.2 二分看起来合理但代价不可逆假设 n 100k 2。二分的直觉做法是先从 50 层扔。如果碎了你只剩 1 个鸡蛋而你还不知道 F 落在 0 到 49 之间的哪个位置只能老老实实从 1 层开始一层一层往上试最坏情况下要再试 49 次加上第 1 次总共 50 次。如果 50 层没碎你接着去 75 层扔一旦在 75 层碎了你还有 1 个蛋要扫 51 到 74 这 24 层最坏再花 24 次总共 1 1 24 26 次。问题的根子在于二分把每次投掷当成等价值的一次信息获取但实际上当你只剩 1 个鸡蛋时每一次投掷的成本结构完全变了——你必须从小到大顺序试一次只能排除一层。所以真正的最优策略既不是纯二分也不是纯线性而是前期步子迈大、随着剩余鸡蛋变少步子自动收窄的混合策略。对 n 100、k 2正确答案是 14 次这个数字后面会反复出现你可以先记下来。1.3 把最坏情况最小化写成数学表达式一旦意识到这是个 min-max 问题就可以把它翻译成形式化的表达。设第一次选择在第 x 层扔那么如果鸡蛋碎了问题变成用 k−1 个鸡蛋确定 0 到 x−1 之间的 F即一个规模更小的子问题如果鸡蛋没碎问题变成用 k 个鸡蛋确定 x 到 n 之间的 F等价于一个 n−x 层楼、k 个鸡蛋的子问题因为下面的 x 层已经被证明安全临界楼层只可能在上方整体往上平移即可。两条分支你无法预知会走哪一条所以必须按最坏的那条算。于是有min over x of ( 1 max( f(k−1, x−1), f(k, n−x) ) )这个表达式是整道题的题眼。它把原问题拆成了两个规模更小的同类问题同时天然带来了两个维度的状态——鸡蛋数和楼层数。剩下的所有工作无非是把这个式子算得快一点、省一点。2. 正向 DP状态定义、转移拆解与三个不能漏的边界2.1 dp[i][j] 的含义与转移方程的逐项解读顺着 1.3 的表达式最自然的状态定义就是dp[i][j]有 i 个鸡蛋、面对 j 层楼即需要确定 F 是否落在 1 到 j 之间最少需要多少次投掷。转移方程写成dp[i][j] 1 min_{1 x j} max( dp[i-1][x-1], dp[i][j-x] )逐项拆开看dp[i-1][x-1]对应在第 x 层扔且碎了的情况下面还有 x−1 层需要确定鸡蛋少了一个dp[i][j-x]对应没碎的情况鸡蛋数量不变但只需要确定 x 之上的 j−x 层外层那个1就是当前这次投掷本身min遍历所有可能的首次投掷楼层 xmax取两条分支里更费劲的那一条。这里有个很多人会写错的地方dp[i][j-x]的第二个下标到底是 j−x 还是 n−(x−1)−1。其实因为楼层的绝对编号不影响答案只影响还剩多少层需要区分所以统一用待确定区间的长度作为状态写法就是 j−x。我建议在实验报告里把这句话写清楚因为阅卷老师很看重状态定义是否自洽。2.2 初始化0 层、1 层、1 个鸡蛋边界条件是这道题最容易翻车的地方因为它同时存在鸡蛋数退化和楼层数退化两个方向。完整的初始化如下条件取值理由dp[i][0] 00没有楼层需要确定一次都不用扔dp[i][1] 11只有 1 层扔一次就能确定 F 是 0 还是 1dp[0][j] INF (j0)无穷大没有鸡蛋却还有楼层要确定不可能完成dp[1][j] jj只剩 1 个鸡蛋必须线性扫描最坏 j 次dp[i][j] INF 初始无穷大作为 min 的初始值特别注意dp[0][j]这一行。很多代码出错就是因为忘了把 i 0 的行设成无穷大导致内层循环里dp[i-1][x-1]取到 0最后算出来的答案小得离谱。另外dp[i][1] 1这一条要在 j 循环开始之前单独填好否则会被转移方程覆盖成一个更差的错误值。2.3 O(k·n²) 在实验规模下到底够不够正向 DP 的时间复杂度是外层 i 循环 k 次、外层 j 循环 n 次、内层 x 循环 n 次合计 O(k·n²)。空间复杂度 O(k·n)。拿实验课上常见的规模估一下如果 n ≤ 1000、k ≤ 100那最坏就是 100 × 1000 × 1000 1 亿次内层操作在 C 里大约 0.3 到 0.5 秒勉强能过同样的规模放到 Python 里就是几分钟直接超时。如果 n 来到 10⁴ 这个级别O(k·n²) 变成 100 × 10⁸ 10¹⁰无论什么语言都救不回来。所以我建议在做实验时先看清楚数据范围n 小的时候写正向 DP 完全够用且好写n 大的时候必须换思路。另外还有一个容易被忽略的优化当 k 很大时多余的鸡蛋其实没有意义。用信息论的角度看每次投掷只有碎和不碎两种结果t 次投掷最多区分 2^t 种情况而要区分 n1 种可能的 F 值需要 2^t ≥ n1所以 t ≥ ⌈log₂(n1)⌉。也就是说当 k ≥ ⌈log₂(n1)⌉ 时鸡蛋已经多到用不完答案恒为 ⌈log₂(n1)⌉。对 n 10⁴log₂(10001) ≈ 13.3所以 k ≥ 14 之后答案固定是 14。做预处理时把 k 截断到 14能省掉大量无用计算。Python 版本的正向 DP 写法如下逻辑最直白适合用来做小规模对拍def super_egg_drop_direct(k: int, n: int) - int: INF float(inf) # dp[i][j]: i 个鸡蛋j 层楼待确定 dp [[INF] * (n 1) for _ in range(k 1)] for j in range(n 1): dp[1][j] j # 1 个鸡蛋只能线性扫 for i in range(1, k 1): dp[i][0] 0 # 0 层不用扔 dp[i][1] 1 # 1 层扔一次 for i in range(2, k 1): for j in range(2, n 1): best INF for x in range(1, j 1): worst max(dp[i - 1][x - 1], dp[i][j - x]) if worst 1 best: best worst 1 dp[i][j] best return dp[k][n]这段代码里我把dp[1][j] j放在最前面单独填再在 i 循环里补dp[i][0]和dp[i][1]顺序上不会互相干扰。如果你把它写成 i 从 1 开始、j 从 1 开始的双层循环就要小心dp[i-1][x-1]在 i 1、x 1 时取到dp[0][0]这个值是 0会让答案偏小——这就是前面说的dp[0][j]行必须处理干净的原因。3. 反向 DP把步数从答案变成状态3.1 一次思路翻转带来的降维打击正向 DP 的瓶颈在于内层那个枚举 x 的循环。要想干掉它最有效的办法是把状态和答案的角色对调一下。正向是给定鸡蛋和楼层求最少步数反过来问就是给定鸡蛋和步数最多能搞定多少层楼。听起来像文字游戏但复杂度直接掉一个量级。具体定义f[t][i]表示有 i 个鸡蛋、最多允许投掷 t 次能够确定的楼层数上限。注意这里说的确定是指用这套资源可以覆盖一个长度为f[t][i]的连续楼层区间无论 F 落在区间内的哪个位置都能锁定它。最终答案就是找到最小的 t使得f[t][k] ≥ n。为什么这个定义能消掉内层枚举因为在正向 DP 里枚举 x 的本质是决定第一次扔哪层而这个问题在反向视角下有了闭式答案——第一次就扔在最优位置上这个位置是可以直接推导出来的不需要试。3.2 f[t][i] f[t-1][i-1] f[t-1][i] 1 的完整推演假设现在有 i 个鸡蛋、t 次机会怎么安排第一次投掷才能覆盖最多楼层答案是把第一次扔在第f[t-1][i-1] 1层。我们来推一遍这个位置是怎么来的。第一次扔完之后分两种情况碎了剩 i−1 个鸡蛋、t−1 次机会这些资源最多能向下覆盖f[t-1][i-1]层所以下面必须恰好留f[t-1][i-1]层。没碎鸡蛋还是 i 个机会还剩 t−1 次这些资源最多能向上覆盖f[t-1][i]层。把下面f[t-1][i-1]层、当前这一层、上面f[t-1][i]层加起来总覆盖长度就是f[t][i] f[t-1][i-1] f[t-1][i] 1这个式子的妙处在于它是纯粹的加法没有任何 min 或 max因为我们已经把最优投掷位置内化进了定义本身。写代码时只需要两层循环复杂度 O(k · t_max)而 t_max 的上界是 n1 个鸡蛋时的答案实际远小于 n。边界也很干净f[0][i] 0一次都不扔什么都确定不了f[t][0] 0没有鸡蛋同样什么都确定不了f[t][1] t1 个鸡蛋 t 次机会最多线性覆盖 t 层。3.3 滚动数组、封顶与一个必须注意的溢出点由于f[t][*]只依赖f[t-1][*]可以用两个一维数组滚动把空间从 O(k·t) 压到 O(k)。C 实现如下#include bits/stdc.h using namespace std; int superEggDrop(int k, int n) { // 鸡蛋数超过 log2(n)1 就没有增益截断可以防止中间值爆掉 int cap 1; while ((1 cap) n 1 cap 31) cap; k min(k, cap); vectorint prev(k 1, 0), cur(k 1, 0); int t 0; while (prev[k] n) { t; for (int i 1; i k; i) { long long v (long long)prev[i - 1] prev[i] 1; // 封顶到 n1避免数值无意义地膨胀 cur[i] (int)minlong long(v, (long long)n 1); } swap(prev, cur); } return t; }这段代码里有三个工程细节值得说。第一prev在循环开始前是全 0 数组正好对应f[0][*] 0第一次迭代算出来的f[1][i] 0 0 1 1语义正确不需要额外初始化。第二long long强制转换不能省当 k 接近 30 时f[t][i]的量级会逼近 2^tint 早就在第 30 多次迭代时溢出了一旦溢出变成负数while (prev[k] n)就会永远为真程序死循环。第三封顶到n 1是个很实用的小技巧因为题目只关心f[t][k]有没有达到 n超出部分的具体数值毫无意义。Python 版本的写法几乎一致适合交到在线判题系统上def super_egg_drop(k: int, n: int) - int: # 鸡蛋过多没有增益先截断 cap 1 while (1 cap) n 1: cap 1 k min(k, cap) prev [0] * (k 1) t 0 while prev[k] n: t 1 cur [0] * (k 1) for i in range(1, k 1): cur[i] min(prev[i - 1] prev[i] 1, n 1) prev cur return t实测下来n 10⁴、k 100 这一组数据反向 DP 在 Python 里跑完大约 1 到 2 毫秒在 C 里基本测不出耗时。这就是状态互换的威力——不是靠常数优化而是直接把内层循环砍掉了。4. 决策单调性与组合数闭式解4.1 正向 DP 也能优化max 函数是单峰的如果你已经写了正向 DP又不想推翻重来重新理解反向状态也可以原地做优化。观察内层那个max( dp[i-1][x-1], dp[i][j-x] )随着 x 从 1 增大到 jdp[i-1][x-1]是单调不减的楼层越多越费劲而dp[i][j-x]是单调不增的楼层越少越省事。一个单调不减的函数和一个单调不增的函数取 max结果必然先降后升是一个单峰离散意义下的凸函数。既然是单峰就可以二分找谷底。具体做法是在[1, j]上二分比较dp[i-1][mid-1]和dp[i][j-mid]的大小关系如果前者小于后者说明谷底在右侧收缩左边界否则收缩右边界。这样内层枚举从 O(n) 降到 O(log n)总复杂度变成 O(k·n·log n)。对 n 10⁴、k 100 来说大约是 100 × 10⁴ × 14 ≈ 1.4 × 10⁷C 里几十毫秒搞定。需要提醒一点这个单峰性是弱单调意义上的也就是可能出现连续相等的平台段。二分的时候如果用严格不等号去收缩边界遇到平台段可能会停在偏离谷底的位置导致结果偏大。稳妥的写法是在二分结束后对邻近的两三个位置再暴力检查一遍取最小值。我自己第一次写这个优化时就栽在这里样例过了但大数据上答案偏大 1排查了半小时才发现是平台段的问题。4.2 两个鸡蛋的闭式解与更一般的组合数形式把反向 DP 的递推式展开可以得到一个很漂亮的闭式解。已知f[t][i] - f[t-1][i] f[t-1][i-1]配合边界f[0][*] 0反复代入就能得到f[t][i] C(t, 1) C(t, 2) ... C(t, i)也就是说i 个鸡蛋、t 次投掷能覆盖的楼层数是组合数C(t, 1)到C(t, i)的累加和。当 i ≥ t 时这个和等于2^t - 1正好对应前面说的信息论上界。这也从组合数学的角度解释了一个反直觉的现象鸡蛋多到一定程度之后再加鸡蛋就完全没用了因为C(t, i)在 i t 时恒为 0。最常用的特例是 i 2此时f[t][2] C(t,1) C(t,2) t t(t-1)/2 t(t1)/2解不等式t(t1)/2 ≥ n就能直接得到两个鸡蛋的答案连代码都不用写。n 100 时13 × 14 / 2 91 10014 × 15 / 2 105 ≥ 100所以答案是 14。4.3 几组必须背下来的手算数字实验考试和面试里经常直接问你具体数字这里整理一张表建议直接记住前几行楼层 n鸡蛋 k答案依据1001100线性扫描10021414×15/2 105 ≥ 100100≥772⁶ 64 1012⁷ 128 ≥ 101100024545×46/2 1035 ≥ 10001000≥10102⁹ 512 10012¹⁰ 1024 ≥ 1001100002141141×142/2 10011 ≥ 1000010000≥14142¹³ 8192 100012¹⁴ ≥ 10001两个鸡蛋、100 层楼的那个 14还可以反推出具体的投掷序列第一次扔 14 层没碎就扔 1413 27 层再没碎扔 2712 39 层依次是 50、60、69、77、84、90、95、99。这个序列的构造逻辑是每次比上一次少走一层这样即使第一个鸡蛋在任意一次碎掉剩下的鸡蛋也刚好够用剩余的次数线性扫完中间那段。你可以自己验证一下如果在 27 层碎了说明 F 落在 15 到 26 之间共 12 层而你已经用了 2 次还剩 12 次刚好够。这个逐步收窄的设计思路比死记硬背数字有价值得多。5. 从 WA 到 AC实验报告里那些扣分点5.1 下标错位待确定区间长度的语义漂移正向 DP 里最常见的一类错误是在写dp[i][j-x]时纠结到底该减多少。有人写dp[i][n-x]用绝对楼层当状态有人写dp[i][j-x-1]把当前层也减掉了结果样例能过、边界数据全挂。根源在于状态定义里 j 的语义没有统一。我的建议是在代码注释里明确写上j 表示待确定的楼层区间长度第 j 层是区间的最顶层这样dp[i][j-x]就是x 之上的 j−x 层dp[i-1][x-1]就是x 之下的 x−1 层加减关系一目了然。写完注释再写代码比写完代码再回头猜要高效得多。反向 DP 里对应的坑是数组下标的起始值。f[t][i]里 i 的取值范围是 0 到 k代码里开vectorint(k 1)就对了但如果你习惯性地写成(k)当 k 1 时访问f[t][1]就越界了而且这种越界在小的测试点上往往不崩到大数据上才随机出错排查起来非常痛苦。5.2 无穷大的选择别用 INT_MAX正向 DP 里需要用一个正无穷来初始化dp数组和best变量。很多人直接写INT_MAX然后在转移时做worst 1结果INT_MAX 1直接溢出成负数min就选到了这个负数整个 DP 表被污染。正确的做法是用0x3f3f3f3f约 10.6 亿而不是INT_MAX约 21.4 亿因为前者的两倍仍然在 int 范围内加一也不会溢出。这个技巧在做滚动数组、加和类 DP 时同样适用属于基本素养。Python 里因为没有整数溢出用float(inf)是安全的但要注意float(inf) 1仍然是inf不会出错。不过如果后面要做整数比较或者取模浮点无穷大会带来类型混乱所以我一般还是用一个足够大的整数常量比如10**9。5.3 多组输入与 k、n 的读取顺序实验题目经常是多组数据格式可能是先给一个 T然后 T 行每行两个整数 k n也可能是读到文件末为止。这里有两个坑。第一k 和 n 的顺序非常容易读反因为题面里有的写成k eggs and n floors有的写成n floors and k eggs代码里一旦顺序反了小数据可能凑巧答案相同大数据立刻错。第二多组数据不重置 DP 数组或者滚动数组会造成上一组的残留值污染尤其是用全局数组的写法必须每轮清空或者重新分配。我的习惯是在读入之后立刻打印一次k和n做人工核对改完再删掉。这个土办法在实验阶段至少帮我省了三次半小时的无效调试。5.4 记忆化搜索的递归深度陷阱有不少人喜欢用记忆化搜索来写正向 DP因为它和递归式的转移方程对应得最自然写起来像数学公式。但递归深度会随 n 增长n 10⁴ 时递归层数可能达到上万层Python 默认递归上限是 1000直接RecursionErrorC 里则是栈溢出表现为段错误。解决办法有两个要么手动sys.setrecursionlimit并承担爆栈风险要么老老实实改成递推。考虑到反向 DP 的递推版本本来就只有十几行我个人的建议是这道题完全没必要用记忆化搜索直接用递推写反向 DP既快又稳。6. 这类 DP 还能往哪延伸6.1 答案做状态是一整类技巧不只是这一题鸡蛋掉落问题的核心技巧是把最少步数从答案变成状态维度转而求给定步数最多能覆盖多少。这个套路在动态规划里有一个通用形态当资源维度很大、而答案维度很小的时候就把答案做成状态资源做成待求的量。最典型的另一个例子是 01 背包的变形——求恰好装满容量 V 时的最小重量或者求达到价值 W 所需的最小容量本质上都是把价值做状态、容量做答案复杂度和原版完全对调。判断该不该用这个技巧有个很实用的经验法则先估一下答案的上界和资源的范围哪个更小。如果答案上界明显小于资源范围就值得考虑互换。鸡蛋掉落里答案上界是 n1 个鸡蛋的线性扫描资源范围是 n 层楼看起来量级差不多但关键在于内层的枚举被完全消掉了这才是真正的收益来源。所以更准确的说法是当把答案做成状态之后能消掉一层枚举时这个互换就值得做。6.2 和经典称球问题的对照如果你对这类最坏情况最小化的问题感兴趣可以拿它和经典的称球问题对照着看。称球问题是12 个外观相同的球里有一个重量不同的用天平最少称几次能找出来。这两个问题的骨架完全一样——都是有限次实验、每次实验有若干种结果、要在最坏情况下用最少次数锁定答案。区别在于分支数鸡蛋掉落的分支数是 2碎 / 不碎天平的分支数是 3左重 / 右重 / 平衡。这就直接导致了两者的信息论下界不同。鸡蛋掉落是 2^t ≥ n 1称球是 3^t ≥ 2412 个球 × 2 种轻重可能性3³ 27 ≥ 24所以答案是 3 次。你可以看到一旦抽象到每次实验能区分多少种结果这个层面具体是鸡蛋还是天平就不重要了剩下的只是分支数的差异。6.3 几个值得自己动手改一改的变体做完基础版之后我建议自己动手改三个变体对理解状态设计帮助很大。第一个是把问题反过来给定 n 层楼和允许的最大投掷次数 t求最少需要多少个鸡蛋。这个变体只要把反向 DP 的外层循环结构调一下就能做出来。第二个是求方案数多少种投掷序列能在最坏 t 次内完成任务。这个需要额外加一维计数复杂度会上去适合拿来练手。第三个是给每次投掷加上不同的成本比如越高楼层扔成本越大此时 min-max 里的那个 1 就不再是常量要替换成位置相关的函数转移方程的结构不变但最优投掷位置会偏移是理解决策单调性的好素材。我个人做完这三个变体之后最大的感受是动态规划的难点从来不在写转移方程而在于选一个能让转移变简单的状态定义。鸡蛋掉落的正向 DP 和反向 DP 用的是同一个问题的两种状态切法代码量差不多复杂度却差了一个量级这种换个角度定义状态的收益比任何常数优化都来得实在。