LeetCode 887 鸡蛋掉落
本题是一道 Google 地经典面试题,很好地考察了动态规划的应用与优化,而且题目重在思路,但最终的解答却并不复杂,实在是一道不可多得的好题。
题目描述
原题链接如下: LeetCode 887 鸡蛋掉落
题目大意
本题不在于考察扔每颗鸡蛋的具体方法,而在于求解扔鸡蛋的次数。而且,要注意不论扔多少次鸡蛋,都要确定无疑地找到分界点。实际上,没种情况下即使扔鸡蛋地方案确定,但是因为分界线不同扔鸡蛋地次数也未必相同,但是有可能找到一个扔鸡蛋次数的上界,保证最多投掷这么多次鸡蛋仍能找到界限。而目的就是找到一种确定地解法,让次数的上界尽量小。
输入与输出
以 K 代表鸡蛋的个数,N 代表楼层的层数。
输入:
|
|
输出:
|
|
解释: 鸡蛋从 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 遍历)。
实际代码
解法一
基本思路:
|
|
初步优化:
|
|
进一步优化:
|
|
解法二
基本思路:
|
|
空间优化:
|
|