LeetCode 887 鸡蛋掉落

2020-04-11 2020-04-11 约 3002 字预计阅读 6 分钟

本题是一道 Google 地经典面试题，很好地考察了动态规划的应用与优化，而且题目重在思路，但最终的解答却并不复杂，实在是一道不可多得的好题。

题目描述

题目大意

本题不在于考察扔每颗鸡蛋的具体方法，而在于求解扔鸡蛋的次数。而且，要注意不论扔多少次鸡蛋，都要确定无疑地找到分界点。实际上，没种情况下即使扔鸡蛋地方案确定，但是因为分界线不同扔鸡蛋地次数也未必相同，但是有可能找到一个扔鸡蛋次数的上界，保证最多投掷这么多次鸡蛋仍能找到界限。而目的就是找到一种确定地解法，让次数的上界尽量小。

输入与输出

以 K 代表鸡蛋的个数，N 代表楼层的层数。

输入：

1
K = 1, N = 2

输出：

1
2

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

解题思路

本题一定要注意不能直觉地直接使用二分法求解 F 地值，因为二分法实际默认查找地次数是不定的，可以随意增长，相比于每层楼都检查一次可以显著减少检查次数。但是，一旦鸡蛋数量过少，有可能发生二分法在最差检查情况完成之前就无鸡蛋可用的情况。不过，实际上我们仍可以从二分法得到启发，假设在楼层 f 扔鸡蛋，最多只可能有两种情况，即：

鸡蛋碎裂：那么 F 不大于 f
鸡蛋不碎：那么 F 大于 f

这样，我们每次扔鸡蛋的操作仍然可以把待检查的楼层分成两部分，之后的操作需要根据扔鸡蛋的情况进行不同的局部检查。

解法一：基本的动态规划

既然已经知道了每次扔鸡蛋都会产生局部检查的子问题，那么就能自然地想到也许可以尝试使用动态规划进行求解，关键则是状态表示方法和状态转换方程的确立。

状态表示方法不难得到，即 dp(i, j) 表示有 i 个鸡蛋，j 个鸡蛋时类似问题的答案，最后本题的结果就是 dp(K, N)。

在确定状态转换方程时，要在 f 层扔鸡蛋之后分情况找出子问题的表示方法：

鸡蛋碎裂：还要使用 K - 1 个鸡蛋在小于 f 层的楼层中检查界限，那么还要查找 dp(K - 1, f - 1) 的子问题
鸡蛋不碎：还要使用 K 个鸡蛋在大于 f 层的楼层种检查界限，那么还要查找 dp(K, j) 的子问题

注意： 在鸡蛋碎裂时，虽然界限有可能时 f，但在 f 层扔鸡蛋的情况已经确定，只要检查小于 f 层的情况就能知道界限是否时 f，无需再使用 f - 1 个鸡蛋重复检查 f 层。

然而，我们其实并不能确定 f 具体是多少，那么就只能对 1 到 N 进行穷举，找到 f 是这些不同楼层的的时候的界限集，然后求出集中数字的最小值即可。

所以，状态转移方程就是：

$$dp(K,\ N) = 1 + \min\limits_{1 \geq f \leq N}{\lbrace \max{(dp(K - 1,\ f - 1),\ dp(K,\ N - f))} \rbrace}$$

而且，初始状态也很好确定，可以明显看出 K 为 1 时，dp(K, N) 的值就是 N，而 N 为 1 时只可能为 1。

初步优化

基本思路的解法要求解 $K \times N$ 个子问题的答案，而每个子问题都要根据楼层数目的不同穷举出不同的投掷方案，所以时间复杂度是 $O(K \times N^2)$。然而，我们要注意到求解每个子问题时，鸡蛋数和楼层数都是确定的，只有枚举值 f 在变化。

首先，不难看出楼层数越多就要用更多的次数来找到答案，即 dp(K, N) 本身是一个关于 N 的单调递增的函数。

这样，在状态转移方程中，一旦 K 和 N 的值确定，那么就有：

dp(K - 1, f - 1) 随 f 递增而递增，最小值为 0
dp(K, N - f) 随 f 递增递减，最小值为 0

这样，在 f 为 1 到 N 之间的连续值时，dp(K - 1, f - 1) 与 dp(K, N - f) 必定在某一点相等，记作 $f_{opt}$，那么在 f 小于 $f_{opt}$ 时，二者最大值为 dp(K, N - f)，f 大于 $f_{opt}$ 时为 dp(K - 1, f - 1)。也就是说，我们实际上在枚举集中求最小值的行为，就是在求必定相交的单调递增线性函数和单调递减线性函数的交点，而求交点的过程完全可以利用函数单调性使用二分法进行查找。

**注意：**这两个单调函数实际上定义域时离散的，但是不影响二分法的使用，可以求定义域集合的左、右中位数，然后比较并求出它们两个对应的函数值的最小值。

这样，我们成功减少了枚举求最值问题的时间复杂度，最后总的时间复杂度是 $O(K \times N \log(N))$

进一步优化

我们已经在上一部分知道 dp(K, N - f) 随 f 递增递减，那么当 K 不变 N 变大的时候，每个 f 对应的函数值都变大了，即它的函数图像会整体右移。那么，只要 N 变大则 dp(K, N - f) 与 dp(K - 1, f - 1) 的交点就会右移，即相应的 $f_{opt}$ 的值就会不断变大。那么，我们只要记录了 N 的值是 n - 1 时的 $f_{opt}$ 的值为 $f_{n-1}$，就能够知道 N 的值是 n 时 $f_{opt}$ 的值要不小于 $f_{n-1}$。这样，即使求解每个 $f_{opt}$ 的时间复杂度都看似都是 O(N)，但实际上每次求解的过程都不会遍历到迭代区间的末尾，而是找到解就结束当前求解过程，然后下一次求解从上一次的解开始。所以，只需要一次从 1 到 N 的遍历就能够求出所有 $f_{opt}$，而总的时间复杂度也就是 $O(K \times N)$。

解法二：逆向思维的动态规划

本题还有另外一种建模思路，即考虑有 K 个鸡蛋和 T 次尝试，最高能够达到多少层楼。这样，可以设 dp(i, j) 表示有 i 个鸡蛋和最多经过 j 次尝试最多可以达到的楼层数。实际上，本题就是求解找到最小的 j 使得 dp(i, j) 不小于 N。

在构造状态转移方程之前，要明白在某个楼层扔鸡蛋，无论结果如何最后无非去它的上部或下部继续检查，而这两个部分的楼层数就又是子问题的状态，即根据第一次尝试鸡蛋是否碎裂：

如果碎裂则查询楼下有多少层楼，即只有 i - 1 个鸡蛋最多进行 j - 1 次尝试可以达到的楼层数
如果不碎则查询楼上有多少层楼，即还有 i 个鸡蛋最多进行 j - 1 次尝试可达到的楼层数

这样，总楼层数就是楼上、楼下楼层数之和再加一，即状态转移方程为：

$$dp(K,\ T) = dp(K,\ T - 1) + dp(K - 1,\ T - 1) + 1$$

**注意：**T 最大不会超过 N，是通过求解 N 层楼实施线性扫描能够有多少次尝试，然后反推出的上界。

空间优化

注意到状态转移方程中右侧子状态只有 T - 1 的情况，那么实际上可以使用一维滚动数组记录状态，节省空间占用。即使用 dp(i) 来表示 i 个鸡蛋能够达到的最大楼层数，只有尝试的次数则可以另外记录，通过不断累加进行搜索。所以当前要求的 dp(K, T) 就是 dp(K)，而 dp(K, T - 1) 和 dp(K - 1, T - 1) 则是上一次搜索的 dp(K) 和 dp(K - 1)。但是，因为数组只有一维，要区分 T - 1 次和 T 次的 dp(K) 只能反向遍历数组（即从 K 到 1 遍历）。

实际代码

解法一

基本思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import kotlin.math.max
import kotlin.math.min

class Solution {
    fun superEggDrop(K: Int, N: Int): Int {
        val dp = Array(K + 1) { IntArray(N + 1) }
        for (i in 1..K) {
            dp[i][1] = 1
        }
        for (i in 1..N) {
            dp[1][i] = i
        }
        for (i in 2..K) {
            for (j in 2..N) {
                dp[i][j] = Int.MAX_VALUE
                for (f in 1..j) {
                    dp[i][j] = min(dp[i][j], max(dp[i][j - f], dp[i - 1][f - 1]) + 1)
                }
            }
        }
        return dp[K][N]
    }
}

初步优化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import kotlin.math.max
import kotlin.math.min

class Solution {
    fun superEggDrop(K: Int, N: Int): Int {
        val dp = Array(K + 1) { IntArray(N + 1) }
        for (i in 1..K) {
            dp[i][1] = 1
        }
        for (i in 1..N) {
            dp[1][i] = i
        }
        for (i in 2..K) {
            for (j in 2..N) {
                var low = 1
                var high = j
                while (low + 1 < high) {
                    val mid = (low + high) / 2
                    val broken = dp[i - 1][mid - 1]
                    val notBroken = dp[i][j - mid]
                    if (broken < notBroken) low = mid
                    else if (broken > notBroken) high = mid
                    else {
                        low = mid
                        high = mid
                    }
                }
                dp[i][j] = 1 + min(
                                    max(dp[i - 1][low - 1], dp[i][j - low]),
                                    max(dp[i - 1][high - 1], dp[i][j - high])
                                )
            }
        }
        return dp[K][N]
    }
}

进一步优化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import kotlin.math.max

class Solution {
    fun superEggDrop(K: Int, N: Int): Int {
        val dp = Array(K + 1) { IntArray(N + 1) }
        for (i in 1..N) {
            dp[1][i] = i
        }

        for (i in 2..K) {
            var f = 1
            for (j in 1..N) {
                while (f < j && max(dp[i - 1][f - 1], dp[i][j - f]) > max(dp[i - 1][f], dp[i][j - f - 1])) f++
                dp[i][j] = 1 + max(dp[i - 1][f - 1], dp[i][j - f])
            }

        }

        return dp[K][N]
    }
}

解法二