给定 k 枚鸡蛋与 n 层楼,问在最坏情况下确定临界层所需的最小操作次数。经典做法是将“最少次数”换个角度建模为“在给定操作次数内最多能确定的楼层数”。
相关算法:动态规划(DP,按操作次数推进)。
核心思路(按“操作次数 m”推进的 DP):
dp[m][e] 表示在最多操作 m 次、手里有 e 枚鸡蛋时,最多能确定的楼层数量。给你 k 枚相同的鸡蛋,以及一栋从第 1 层到第 n 层共有 n 层的建筑。存在某一楼层 f(0 ≤ f ≤ n),使得:
f 的楼层扔下鸡蛋一定会碎;f 楼层或更低楼层扔下鸡蛋不会碎。每次操作可选择任一未碎鸡蛋,从任一楼层 x(1 ≤ x ≤ n)扔下。若鸡蛋碎则不可再用;若没碎可再次使用。请计算确定 f 的确切值所需的最少操作次数(最坏情况)。
k 和 n,表示鸡蛋数量与楼层数。
(可接受用空格或逗号分隔,如 3 14 或 3,14)输入
1 2
输出
2
输入
2 6
输出
3
输入
3 14
输出
4