[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层扔鸡蛋，有两种结果：
- 鸡蛋碎了，这个时候鸡蛋少了一个，楼层也少一个，此时它的最优解是
dp(k-1,i-1)+ 1。 - 鸡蛋没碎，这个时候鸡蛋没少，楼层少了一个，最优解是
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++代码：
int dp(int k, int n, vector<vector<int>> &v) {
int i, f = INT_MAX, dpi;
if (k == 1) return n;
if (n == 0) return 0;
// v数组默认全是-1
if (v[k][n] != -1) {
return v[k][n];
}
// 遍历所有楼层
for (i = 1; i <= n; i++) {
// 计算出第i层的最优解
dpi = max(dp(k - 1, i - 1, v), dp(k, n - i, v)) + 1;
// 计算所有楼层的最小值
f = min(f, dpi);
}
v[k][n] = f;
return f;
}时间复杂度
计算所有的鸡蛋+楼层组合需要时间复杂度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]的遍历改成二分法来遍历，找到这个最小值。代码如下：
int dp(int k, int n, vector<vector<int>> &v) {
int i, f = INT_MAX;
int low, high, mid, broken, not_broken;
if (k == 1) return n;
if (n == 0) return 0;
if (v[k][n] != -1) {
return v[k][n];
}
low = 1;
high = n;
while (low <= high) {
mid = (low + high) / 2;
// 鸡蛋碎了
broken = dp(k - 1, mid - 1, v);
// 鸡蛋没碎
not_broken = dp(k, n - mid, v);
if (broken > not_broken) {
high = mid - 1;
f = min(f, broken + 1);
} else {
low = mid + 1;
f = min(f, not_broken + 1);
}
}
v[k][n] = f;
return f;
}修改后再测试上面超时的数据，只要4毫秒就可以执行完了，效率提高了几百倍：
再次提交代码，通过了（耗时较高）：
把遍历变成二分后，遍历的O(N)变成了O(logN)，所以总的时间复杂度是：O(KN*logN)，空间复杂度是O(KN)。
四、终极动态规划
以dp[k][m]表示k个鸡蛋扔m次最多可以确定的多少层的楼，那么第一个大于等于n的下标m就是扔鸡蛋的次数了。到第i层的时候，依旧是有两种策略：
- 鸡蛋碎了，此时鸡蛋减1，扔的次数减1，接下来可以检测出来的楼层是
dp[k-1][m-1]。 - 鸡蛋没碎，扔的次数减1，接下来可以检测出来的楼层是
dp[k][m-1]。
所以第i个鸡蛋能确定的楼层的总数是：dp[k-1][m-1] + dp[k][m-1] + 1，即鸡蛋碎了的时候能确定的楼层数加上鸡蛋没碎的时候能确定的楼层数再加上本层。
代码：
// k是鸡蛋个数，n是楼层，两个都大于等于1
int superEggDrop(int k, int n) {
int i, j;
vector<vector<int>> v(k + 1, vector<int>(n + 1, 0));
for (j = 1; v[k][j - 1] < n; j++) { // 扔鸡蛋的次数
for (i = 1; i <= k && v[k][j - 1] < n; i++) { // 鸡蛋个数
v[i][j] = v[i - 1][j - 1] + v[i][j - 1] + 1;
}
}
return j - 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)。
int superEggDrop(int k, int n) {
int i, j;
vector<vector<int>> v(k + 1, vector<int>(2, 0));
// 第0列作为前一列的备份列，第1列作为当前列
for (j = 1; v[k][0] < n; j++) {
for (i = 1; i <= k && v[k][j - 1] < n; i++) {
v[i][1] = v[i - 1][0] + v[i][0] + 1;
}
// 拷贝第1列到第0列
for (i = 0; i <= k; i++) {
v[i][0] = v[i][1];
}
}
return j - 1;
}
