鸡蛋掉落

鸡蛋掉落问题，双蛋问题延伸

题目

你将获得 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 层扔下，两种情况：

1. 鸡蛋不碎

   鸡蛋个数仍然是 K，楼层是 X 层到 N 层，即 N-X 层楼。

   状态为 f(K, N-X)

2. 鸡蛋碎了

   鸡蛋个数为 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)))

寻找规律

1. f(K, N)

   在鸡蛋数 K 固定的情况下，楼层数 N 越多，需要的步数一定不会变少

   所以，当 K 不变时，f(K, N) 随着 N 单调递增

2. f(K, N-X)

   同上，K 和 N 不变时，f(K, N-X) 随 X 的增加而单调递减

3. 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 的取值只能是整数，所以我们需要取得这两个函数（想象中的）交点左右两侧最近的整数

题解

def super_egg_drop(K, N):
    """
    @param K: int
    @return: int
    """
    store = {}
    def dp(k, n):
        if (k, n) not in store:
            if n == 0:
                # 0 层楼
                result = 0
            elif k == 1:
                # 1 个鸡蛋，需要扔 n 次
                result = n
            else:
                low, high = 1, n
                # 二分搜索
                while low + 1 < high:
                    x = (low + high) // 2
                    t1 = dp(k-1, x-1)
                    t2 = dp(k, n-x)
                    if t1 < t2:
                        low = x
                    elif t1 > t2:
                        hight = x
                    else:
                        low = hight = x
                result = 1 + min(max(dp(k-1, x-1), dp(k, n-x)) for x in (low, high))

            # 记录已经算过的值
            store[(k, n)] = result
        return store[(k, n)]

    return dp(K, N)