鸡蛋掉落
鸡蛋掉落问题,双蛋问题延伸
题目
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
示例
输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
题解思路
思路:动态规划 + 二分搜索
状态转移方程式
K 个鸡蛋,N 层楼,即 f(K, N)
假设从 X 层扔下,两种情况:
鸡蛋不碎
鸡蛋个数仍然是 K,楼层是 X 层到 N 层,即 N-X 层楼。
状态为 f(K, N-X)
鸡蛋碎了
鸡蛋个数为 K-1,楼层为 1 层到 X-1 层,即 X-1 层楼。
状态为 f(K-1, X-1)
若在 最坏情况下(也就是无论 F 的值如何) f(K, N) 的值最小
我们必须保证 鸡蛋碎了之后接下来需要的步数 和 鸡蛋没碎之后接下来需要的步数 二者的最大值是最小的
由于不知道具体的 F 值,X 取值范围是 1 到 N
f(K, N) = 1 + max[1<=X<=N](min(f(K, N-X), f(K-1, X-1)))
寻找规律
f(K, N)
在鸡蛋数 K 固定的情况下,楼层数 N 越多,需要的步数一定不会变少
所以,当 K 不变时,f(K, N) 随着 N 单调递增
f(K, N-X)
同上,K 和 N 不变时,f(K, N-X) 随 X 的增加而单调递减
f(K-1, X-1)
同上,K 和 N 不变时,f(K-1, X-1) 随 X 的增加而单调递增
由于我们相求的是 f(K, N-X) 和 f(K-1, X-1) 这两个函数的最小的最大值
根据上述函数特性可知,求得 f(K, N-X) 和 f(K-1, X-1) 的交点即可
由于 X 的取值只能是整数,所以我们需要取得这两个函数(想象中的)交点左右两侧最近的整数
题解
1 | def super_egg_drop(K, N): |