前段时间尝试开始写了一波简书，被我的小伙伴嘲笑了一波，说我写的没有什么难度，让我来一道摔鸡蛋，今天刚好有空，接受他的挑战直接来一道困难的鸡蛋掉落问题。题目如下：
题目链接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
思路：
这题目第一眼看下去确实没有很大的思路，题目大概意思是说给你有限个鸡蛋（鸡蛋摔坏了就没了），然后让你在一个N层楼高的楼层去摔，用最少的次数找到鸡蛋在那一层才会被摔碎。
那我们先来屡一下思路，往简单点想：
假如我们有无限个鸡蛋，有100层楼高，是不是就像猜数字一样，在1-100里面猜数字，没有猜对，主持人会告诉你大了还是小了的游戏（碎了就是大了，没碎就是小了），那我们肯定无脑选择中间值去摔，先在50层摔，如果碎了，就在1-49层去再找中间值摔，如果没碎，就去51-100层找中间值摔。每次折半，我们需要log（100）次也就是7次。
假如我们只有一个鸡蛋，有100层楼高，我们还能不能像刚才那样从50层开始摔呢？很明显是不能，因为一旦我们从50层开始摔，万一鸡蛋碎了，后面我们就没有鸡蛋可以去摔了，我们承担不起鸡蛋被摔碎了的风险，所以如果只有1个鸡蛋，我们被迫只能脚踏实地从第一层开始摔，如果没有碎，再一层一层往上摔。如果鸡蛋在100层才碎，我们最终将会摔100次，所以我们需要的次数就是100次。
那假如我们有两个鸡蛋，有100层楼高，这就不一样了，我们有了基本，可以从高一点的楼层摔，如果摔碎了，我们还有一个鸡蛋可以再一层一层摔，但是这就有个问题了，从高一点的楼层摔是多高呢？如果从50层摔，碎了，我们要再摔50次，没碎我们就相当于从51-100层摔2个鸡蛋，具体的次数等同于我们有两个鸡蛋，有50层楼高的这样一种情况，肯定是低于50次的，但是按照总次数来说肯定还是选择最坏情况50次，那么这是不是最优解呢？会不会从33层摔下去，次数更低呢？
当想到这里，很容易的看出来，当碎了和没碎的情况所需要的次数相等时（或者是最接近时），次数更低。那么也就是说我们想要知道从那一层开始摔是最好的，必须一层一层遍历去判断。当我们遍历到第10层时，碎了的情况的次数就等同于（我们只有一个鸡蛋【这里考了一道小学数学题：两个鸡蛋碎了一个还有多少个？】，有9层楼高），没碎的情况就等同于（我们有两个鸡蛋【这里又考了一道小学数学题：两个鸡蛋摔了一个没碎还有多少个？】，有90层楼高）。当分析到这里，我们要求有两个鸡蛋，有100层楼高的情况，就需要知道一个鸡蛋9层楼和两个鸡蛋90层楼的解，也就是原题目子问题的解，很明显的动态规划的思路。
解析：
使用DP去实现，按照题目意思定义一个dp[105][10005]数组，dp[x][y]代表x个鸡蛋y层楼的最优解。初始化为0。
把x=1的全赋值为y代表只有一个鸡蛋的情况下，最优解为楼层数。
然后从x=2开始动态规划求解每一个子问题的最优解。
代码如下：
class Solution {
public:
int dp[105][10005] = { 0 };
int superEggDrop(int K, int N) {
if (K == 1) return N;
if (dp[K][N]) return dp[K][N];
for (int y = 1; y <= N; ++y) dp[1][y] = y;
for (int x = 2; x <= K; ++x)
{
for (int y = 1; y <= N; ++y)
{
int minNUM = y;
for (int i = 1; i <= y; ++i)
{
int temp = std::max(dp[x - 1][i - 1], dp[x][y - i]) + 1;
if (temp < minNUM) minNUM = temp;
}
dp[x][y] = minNUM;
}
}
return dp[K][N];
}
};
优化：
通过了所有样例，但是超时，这是在意料之中，K=100，N=10000这么大的数据规模，每一个子问题的解都要遍历N遍，时间复杂度为O(K*N*N)，高达10^10。
那么要怎么优化呢？如果要使用动态规划的话，K*N的子问题是无可避免的，我们只能去优化求解每个子问题的时间。
刚才我们每次求解子问题都是从i=1遍历到i=N，那么在这个遍历过程中，碎了的情况一开始肯定是最小的1次，逐步变大到N次。同时没碎的情况的次数肯定是从大到小的一个过程。在这样有规律的情况下，我们可以使用二分去优化。
优化后代码如下：
class Solution {
public:
int dp[105][10005] = { 0 };
int superEggDrop(int K, int N) {
if (K == 1) return N;
if (dp[K][N]) return dp[K][N];
for (int y = 1; y <= N; ++y) dp[1][y] = y;
for (int x = 2; x <= K; ++x)
{
for (int y = 1; y <= N; ++y)
{
int minNUM = y;
int i = 1;
int j = y;
while (i <= j)
{
int m = i + ((j - i) >> 1);
int broken = dp[x - 1][m - 1];
int enbroken = dp[x][y - m];
int temp = std::max(broken,enbroken) + 1;
if (temp < minNUM) minNUM = temp;
if (broken < enbroken) i = m + 1;
else j = m - 1;
}
dp[x][y] = minNUM;
}
}
return dp[K][N];
}
};
虽然通过了，但是在速度上只击败了6%的用户，说明还有更快的方法。
计算可知动态规划加二分优化的时间复杂度为O(K*N*logN)
网友评论