知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 扔鸡蛋问题 ## 题目 有 **2 个鸡蛋**和一座 **100 层**的大楼。鸡蛋从某一层及以上扔下会碎,从该层以下不会碎。求在最坏情况下,最少需要扔多少次才能确定这个"临界楼层"? ## 大白话理解 你在一栋 100 层的楼下,手里只有 2 个鸡蛋。鸡蛋有个特性:存在一个楼层 F,从 F 及以上扔下去会碎,从 F-1 及以下不会碎。你必须找到这个 F。 ``` 关键约束: 1. 如果鸡蛋没碎,可以捡回来继续用 2. 如果鸡蛋碎了,就永远失去了 3. 你只有 2 个鸡蛋 目标:最小化最坏情况下的尝试次数 ``` --- ### 为什么不能二分? ``` 常规想法(2个鸡蛋,100层): "我从 50 楼扔第一个鸡蛋" 结果 1:50 楼碎了 → 只剩 1 个蛋,必须从 1 楼开始一层层试到 49 楼 最坏 49 次 ← 非常差! 结果 2:50 楼没碎 → 两个蛋完好,从 51~100 继续二分 每次二分都能复用蛋 问题:第一个蛋碎了之后,只剩一个蛋,只能线性扫描。 所以第一个蛋的策略要小心:不要一次跳得太高。 ``` --- ### 动态规划推导 #### 定义状态 ``` dp[k][n] = 有 k 个鸡蛋、n 层楼需要检验时,最坏情况下的最小尝试次数 ``` #### 转移方程 ``` 假设第一个鸡蛋从第 x 层扔下: 情况 1:碎了 → 还剩 k-1 个鸡蛋,需要检验 1 ~ x-1 共 x-1 层 → 次数 = dp[k-1][x-1] + 1 情况 2:没碎 → 还剩 k 个鸡蛋,需要检验 x+1 ~ n 共 n-x 层 → 次数 = dp[k][n-x] + 1 最坏情况取最大值:max(dp[k-1][x-1], dp[k][n-x]) + 1 我们选择最优的 x(使最坏情况最小): dp[k][n] = min_{1 ≤ x ≤ n} { max(dp[k-1][x-1], dp[k][n-x]) + 1 } ``` #### 2 个鸡蛋、100 层的计算 ``` 边界条件: dp[1][n] = n (只有 1 个蛋,只能从 1 开始一层层试) dp[k][0] = 0 (0 层楼不需要试) dp[k][1] = 1 (1 层楼试 1 次) 现在我们算 dp[2][n] 从 1 到 100: dp[2][1] = 1 dp[2][2] = min{ max(dp[1][0], dp[2][1])+1, ← x=1 max(dp[1][1], dp[2][0])+1 } ← x=2 = min{ max(0,1)+1, max(1,0)+1 } = min{ 2, 2 } = 2 继续递推... 最终:dp[2][100] = 14 ``` --- ### 最优策略:等差数列 ``` 不用 DP 也能直接推导最优策略: 第一个鸡蛋的尝试楼层应该满足: "每次跳跃越来越小,使得无论鸡蛋在哪一层碎,总尝试次数固定" 设第 1 次从 f₁ 层扔,第 2 次从 f₂ 层扔,... 如果鸡蛋在 f₁ 层碎了: 最多需要 (f₁ - 1) 步逐一尝试 但已经试了 1 步(在 f₁ 扔) 所以总次数 = 1 + (f₁ - 1) = f₁ ← 应该等于目标值 更准确的思路(等差数列): 第一次从 x 层扔 第二次从 x + (x-1) 层扔 第三次从 x + (x-1) + (x-2) 层扔 ... 等差数列求和:x + (x-1) + (x-2) + ... + 1 ≥ 100 → x(x+1)/2 ≥ 100 解:x(x+1) ≥ 200 x ≈ 13.6 → x = 14 验证:14+13+12+...+1 = 14×15/2 = 105 > 100 ✓ ``` ``` 最优扔鸡蛋序列: 第 1 次:14 楼 第 2 次:14+13 = 27 楼 第 3 次:27+12 = 39 楼 第 4 次:39+11 = 50 楼 第 5 次:50+10 = 60 楼 第 6 次:60+9 = 69 楼 第 7 次:69+8 = 77 楼 第 8 次:77+7 = 84 楼 第 9 次:84+6 = 90 楼 第 10次:90+5 = 95 楼 第 11次:95+4 = 99 楼 第 12次:99+3 = 102 → 超过 100,不用 此时如果 99 没碎就在 100 层试 最坏情况:第一次在 14 楼就碎了 → 1 + 13 = 14 步 前 13 步都没碎,最后在 99~100 范围确定 → 13 + 1 = 14 步 无论哪种情况,最坏都是 14 次! ``` ``` ASCII 图解: 100F ┤ 99F ┤ ← 第 11 次 95F ┤ ← 第 10 次 90F ┤ ← 第 9 次 84F ┤ ← 第 8 次 77F ┤ ← 第 7 次 69F ┤ ← 第 6 次 60F ┤ ← 第 5 次 50F ┤ ← 第 4 次 39F ┤ ← 第 3 次 27F ┤ ← 第 2 次 14F ┤ ← 第 1 次 1F ┤ └────────────────── 间隔:14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4 ``` --- ### Java 代码:通用 DP ```java /** * K 个鸡蛋 N 层楼,最坏情况下最少尝试次数 */ public int superEggDrop(int K, int N) { // dp[k][n] = k 个鸡蛋,n 层楼的最少次数 int[][] dp = new int[K + 1][N + 1]; // 初始化:1 个鸡蛋只能线性扫描 for (int n = 1; n <= N; n++) { dp[1][n] = n; } // dp[k][0] = 0 默认 // dp[k][1] = 1 默认 for (int k = 2; k <= K; k++) { for (int n = 1; n <= N; n++) { dp[k][n] = Integer.MAX_VALUE; // 遍历可能的第一个投掷楼层 x for (int x = 1; x <= n; x++) { // 碎了:dp[k-1][x-1] + 1 // 没碎:dp[k][n-x] + 1 int worst = Math.max(dp[k - 1][x - 1], dp[k][n - x]) + 1; dp[k][n] = Math.min(dp[k][n], worst); } } } return dp[K][N]; } ``` ```java /** * 优化版:二分搜索代替线性遍历 x * 因为 dp[k-1][x-1] 随 x 递增,dp[k][n-x] 随 x 递减 * 它们的 max 是一个"山谷"形,可以用二分找最低点 */ public int superEggDrop(int K, int N) { int[][] dp = new int[K + 1][N + 1]; for (int n = 1; n <= N; n++) dp[1][n] = n; for (int k = 2; k <= K; k++) { for (int n = 1; n <= N; n++) { int lo = 1, hi = n; while (lo + 1 < hi) { int x = lo + (hi - lo) / 2; int broken = dp[k - 1][x - 1]; int unbroken = dp[k][n - x]; if (broken < unbroken) { lo = x; // 交点在右边 } else if (broken > unbroken) { hi = x; // 交点在左边 } else { lo = hi = x; // 刚好相等 } } dp[k][n] = 1 + Math.min( Math.max(dp[k - 1][lo - 1], dp[k][n - lo]), Math.max(dp[k - 1][hi - 1], dp[k][n - hi]) ); } } return dp[K][N]; } ``` --- ### 延伸:K 个鸡蛋 N 层楼 ``` 如果不限制鸡蛋数: 最少次数 = ⌈log₂(N+1)⌉(纯二分) 如果鸡蛋无限多但只关心最少尝试次数: 可以直接二分 如果鸡蛋 >> 次数: 可以让每次尝试都跨度更大 ``` --- ## 一句话总结 2 个鸡蛋 100 层楼,最少 14 次。策略是用等差数列 14,13,12,... 递减跳跃,保证无论鸡蛋在哪一层碎,总尝试次数都固定在 14。推广到 K 个鸡蛋 N 层楼,用 DP:`dp[k][n] = min(max(dp[k-1][x-1], dp[k][n-x])+1)`。 --- 下一篇:[06 - 海盗分金币](./06-pirate-gold.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入