鸡蛋掉落

难度: Hard

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：

输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

示例 2：

输入：k = 2, n = 6
输出：3

示例 3：

输入：k = 3, n = 14
输出：4

提示：

1 <= k <= 100
1 <= n <= 10⁴

Submission

运行时间: 2512 ms

内存: 43.4 MB

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()

        def dp(K, N):
            if (K, N) in memo:
                return memo[(K, N)]
            if K == 1:
                return N
            if N == 0:
                return 0
            res = float('INF')
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K-1, mid-1)
                not_broken = dp(K, N-mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            memo[(K, N)] = res
            return res
        return dp(K, N)

Explain

问题本质是一个动态规划问题，目标是找到最小的测试次数以确定鸡蛋不会碎的最高楼层。动态规划的状态是dp(K, N)，表示有K个鸡蛋和N层楼时确定楼层的最小测试次数。如果从第X层扔鸡蛋，会有两种情况：1) 鸡蛋碎了，需要考虑下方的X-1层楼，用K-1个鸡蛋继续测试；2) 鸡蛋没碎，需要考虑上方的N-X层楼，用K个鸡蛋继续测试。考虑最坏情况，应取两种情况的最大值加1（本次测试）。为了优化查找过程，使用二分搜索来确定最小的最大测试次数，即找到使得两种情况平衡的楼层X。使用记忆化来避免重复计算相同的子问题。

时间复杂度: O(K * N * logN)

空间复杂度: O(K * N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()

        def dp(K, N):
            # 如果已解决此子问题，返回存储的结果
            if (K, N) in memo:
                return memo[(K, N)]
            # 如果只有一个鸡蛋，需要从1层测试到N层
            if K == 1:
                return N
            # 如果没有楼层，不需要测试
            if N == 0:
                return 0
            res = float('INF')
            lo, hi = 1, N
            # 使用二分搜索优化找到最小的最大测试次数
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K-1, mid-1)
                not_broken = dp(K, N-mid)
                # 根据二分的结果调整搜索区间和记录结果
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            # 记录当前(K, N)的最优解
            memo[(K, N)] = res
            return res
        return dp(K, N)

Explore

二分搜索通过逐步缩小搜索区间，来找到一个楼层X，使得在这一层楼X扔鸡蛋时两种情况（鸡蛋碎或不碎）的最坏测试次数最接近。如果从这个楼层扔鸡蛋，鸡蛋碎了，则测试下方的楼层需要的最大次数是broken；如果鸡蛋没碎，测试上方楼层需要的最大次数是not_broken。我们的目标是最小化这两种情况的最大值，即minimize max(broken, not_broken)。通过调整二分搜索的上下界，可以找到一个最小的这样的最大值，即达到最优解。

当broken > not_broken时，意味着从楼层mid向下的测试次数（鸡蛋碎的情况）比向上的测试次数（鸡蛋没碎的情况）更多。这表明，测试的最坏情况主要集中在楼层较低的一半，因此应该尝试更低的楼层以尝试找到更平衡的情况，从而减小最坏情况的测试次数。因此，调整搜索区间的上界为mid - 1，以探索较低楼层是否可以得到更优的结果。

当只有一个鸡蛋时，必须从第1层开始逐层向上测试，直到找到鸡蛋碎的那一层，以确保最坏情况下能确定鸡蛋不会碎的最高楼层。因此，需要测试从1层到N层，最坏的情况是需要测试N次（即每一层都要测试一次）。这里的N代表了在只有一个鸡蛋的情况下，确定鸡蛋不会碎的最高楼层所需的最大测试次数。

基本情况'如果没有楼层，不需要测试'是基于这样的考虑：如果没有楼层（N=0），那么不需要进行任何测试，因为没有楼层可供检测鸡蛋是否会碎。这个逻辑意味着在楼层数为0的情况下，问题已经自然解决，因为没有需要进行测试的楼层。因此，这种情况下的最小测试次数是0。