[leetcode]887-鸡蛋掉落

来源：力扣 （LeetCode）

链接：https://leetcode-cn.com/problems/super-egg-drop

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

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

每次移动，你可以取一个鸡蛋 （如果你有完整的鸡蛋） 并把它从任一楼层 X 扔下 （满足 1 <= X <= N） 。

你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 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 <= 10000

二、动态规划+递归

看到题目的第一眼就能想到得用动态规划来解题了，关键是如何来定义动态规划的状态和状态转移方程。

比较容易想到的是以 dp(k, n)来表示 k 个鸡蛋在 n 层建筑时需要扔鸡蛋的最小次数，它的最优状态肯定是从前面的 1-n 层楼中取，谁的状态越优，就取谁的。也就是说，在那一层扔鸡蛋需要的次数最少，就是谁。那么：

$$dp(k,n)=min(dp(k,1), dp(k,2), ..., dp(k,n))$$

在第 i 层扔鸡蛋，有两种结果：

1. 鸡蛋碎了，这个时候鸡蛋少了一个，楼层也少一个，此时它的最优解是 dp(k-1,i-1) + 1 。
2. 鸡蛋没碎，这个时候鸡蛋没少，楼层少了一个，最优解是 dp(k,n-i) + 1 。

可以参考这张图片：

图片来源：labuladong

后面的 dp[k][n]和 dp(k, n) 是一个意思。

为什么没碎之后是 dp[k][n-i]，因为没碎的话，鸡蛋还是 k 个，而楼层只有 n-i 了，所以只要找出 dp[k][n-i]就可以了。

计算出来这两种情况后，要选择最坏情况下的场景，所以要取两者的最大值。总结出来状态转移方程就是：

\(\begin{equation} dp[k][i]= \begin{cases} 1 & k=1 \\ 0 & n=0\\ max(dp[k-1][i-1], dp[k][n-i]) & k>1,n>0 \end{cases}\end{equation}\)

归纳成 C++代码：

时间复杂度

计算所有的鸡蛋+楼层组合需要时间复杂度 O(KN)，每个楼层取最优值是 O(N)，总体的时间复杂度是：

$$O(K*N^2)$$

这个时间复杂度还是很大的，可以说迄今为止我还没见过这么高复杂度的动态规划。提交后果然超时了：

在本地测试这组数据发现需要执行 2s+才能计算出来 （CPU 是 I5-8400 主频 2.8GHz），所以提交肯定会超时：

三、动态规划+二分

超时之后不得不想办法优化，优化前为了确定在哪个楼层扔鸡蛋最优不得不从 1 遍历到 n，这个时间复杂度是 O(N) 太长了，实际上可以使用二分法来找出最优解，讲 O(N) 变成 O(logN) 。

上面已经求出了状态转移方程是 max(dp[k-1][i-1], dp[k][n-i])，其中可以知道的是，dp[k-1][i-1]是随着 i 逐步递增的，因为楼层越高，需要扔的次数肯定也越多。而 dp[k][n-i]是跟随 i 递减的，因子 i 是负数，i 越大，n-i 越小，扔的次数也越小。

上面的状态转移方程就是现在所有楼层的最大值中，找到最小值，如图所示：

红色的线表示的是两个子状态中的最大值，两根线的交点正好就是所有最大值中的最小值。那么根据这个规律，就可以把 i∈[1, n]的遍历改成二分法来遍历，找到这个最小值。代码如下：

修改后再测试上面超时的数据，只要 4 毫秒就可以执行完了，效率提高了几百倍：

再次提交代码，通过了 （耗时较高）：

把遍历变成二分后，遍历的 O(N) 变成了 O(logN)，所以总的时间复杂度是：O(KN*logN)​，空间复杂度是 O(KN) 。

四、终极动态规划

以 dp[k][m]表示 k 个鸡蛋扔 m 次最多可以确定的多少层的楼，那么第一个大于等于 n 的下标 m 就是扔鸡蛋的次数了。到第 i 层的时候，依旧是有两种策略：

1. 鸡蛋碎了，此时鸡蛋减 1，扔的次数减 1，接下来可以检测出来的楼层是 dp[k-1][m-1]。
2. 鸡蛋没碎，扔的次数减 1，接下来可以检测出来的楼层是 dp[k][m-1]。

所以第 i 个鸡蛋能确定的楼层的总数是：dp[k-1][m-1] + dp[k][m-1] + 1，即鸡蛋碎了的时候能确定的楼层数加上鸡蛋没碎的时候能确定的楼层数再加上本层。

代码：

要注意的地方是循环条件终止条件是 v[k][j-1] >= n，为什么是 j-1 呢，因为第一层 for 循环的 j 表示的是第 j 次扔鸡蛋能确定的层数，此时层数还没有确定，还要在下面的循环中计算得到。如果使用 v[k][j]会出现死循环导致数据溢出。

时间复杂度 O(K*N)，提交后执行用时大大减少：

继续优化

上面已经计算出来状态转移方程是：

$$dp[k][i]=dp[k-1][i-1] + dp[k][i-1] + 1$$

可以看到，当前状态实际上只与前面一列的状态有关，可以只保存前面一列状态的数据，空间复杂度为 O(K) 。