LeetCode 887. 鸡蛋掉落
难度：Hard
题目简介
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
思路分析
- 首先来整理一下题目内容：我们有k个鸡蛋，并且需要找出该栋楼中的某层f，使得高于f层时扔鸡蛋一定会碎，低于f层时一定不会碎；我们每一次可以拿没有碎的鸡蛋去尝试，求问能够确定f的最小操作次数是多少？
- 很直观的想法就是运用动态规划思想解题，定义二维数组
drop[i][j]，其表示当手上的鸡蛋只有i个时，当前总楼层为j时，咱们能够确定f的最小操作次数即为drop[i][j]。状态转移方程实际上相对比较简单，当我们在楼层x抛下一枚鸡蛋时，假设鸡蛋碎了，那么鸡蛋数量-1，同时我们可以确定此时f层只能够在x层以下；假设鸡蛋没碎，那么我们可以确定f层只能够在x层或者以上：drop[i][j] = 1 + min(max(drop[i-1][j-1], drop[i][n-j])) where 1 <= j <= n - 对于该状态转移方程，首先
1代表着当前扔鸡蛋这次操作，然后drop[i-1][j-1]代表着此时扔下鸡蛋破碎之后，可以确定f层肯定是在j层以下，所对应的最小操作次数。drop[i][n-j]代表扔下鸡蛋没碎，可以确定f层肯定是在j层或者以上的最小操作次数，由于我们需要找到最坏情况下的最小操作次数，所以两者必须取最大值max。同时，对于在不同楼层扔下鸡蛋这个操作，我们需要取所得最小值的楼层从而使得最坏情况下的操作次数最少 - 如果我们直接暴力转移求解每个状态的 \textit{dp}dp 值，时间复杂度是为 O(kn^2)，即一共有 O(kn)个状态，对于每个状态枚举扔鸡蛋的楼层 x，需要 O(n)的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。此处官方采用了二分查找的思想成功优化了枚举的时间复杂度，感兴趣的小伙伴可以戳此链接：https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2/
思路拓展
- 关于官方的数学证明与解释，我反反复复看了好几遍都觉得难以记下，个人觉得过于复杂繁琐，于是乎不在此附上其代码和解释，而是转换思想进行简单明了的题目解答
- 首先抛开刚才的过程，我们可以改变一下求解的思路，求k个鸡蛋在操作次数为m时最多可以确定的楼层数量：假设
dp[k][m]表示k个鸡蛋在m步内最多能测出的层数。那么，问题可以转化为当k <= K时，找一个最小的m，使得dp[k][m]<= N - 我们来考虑下求解dp[k][m]的策略：
- 假设我们有k个鸡蛋第m步时，在第X层扔鸡蛋。这时候，会有两种结果，鸡蛋碎了，或者没碎
- 如果鸡蛋没碎，我们接下来会在更高的楼层扔，最多能确定 dp[k][m-1] 层的状态
- 如果鸡蛋碎了，我们接下来会在更低的楼层扔，最多能确定 dp[k-1][m-1] 层的状态
- 因此，这次扔鸡蛋，我们最多能测出 dp[k-1]m-1 + dp[k][m-1] (没摔碎时能确定的层数) + 1 (本层) 层的结果。
- 另外，我们知道一个鸡蛋一次只能测一层，没有鸡蛋一层都不能测出来。
- 如果移动步数m=0，那么一层都无法确定；如果鸡蛋个数为1，那么我们在m步内最多能确定m层的状态
- 动态规划的终止条件为：此时能够确定的层数为N，返回此时的m值，为最小的移动步数
- 因此我们可以列出完整的递推式:
dp[k][0] = 0 dp[1][m] = m (m > 0) dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 (k > 0, m>0)
代码实现
class Solution {
public:
int superEggDrop(int K, int N) {
if(K==0) return 0;
if(K==1) return N;
int dp[N+2][K+2];
memset(dp,0,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=N;++i)
{
dp[i][0]=0;
for(int j=1;j<=K;++j)
{
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1;
if(dp[i][j]>=N)
return i;
}
}
return N;
}
};