你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F的值的最小移动次数是多少？
关键词
- 直觉的错误性
- 最优解无规律
- 动态规划
- 暴力解法的重要性
扩展待补充
- 决策单调性和动态规划
- 自顶而下和自底而上的动态规划
初始反应
看到这个题第一个反应：这是动态规划，还认真地在注释处备注了一下。然后事情开始向意外的方向发展……因为动态规划是可以优化的嘛，所以也没有很认真地理清逻辑关系，总觉得可以更简单一点。于是二分法上线，具体代码如下：
/**动态规划？
* 一个鸡蛋，要N次
* K个鸡蛋，可以先用K-1个鸡蛋二分法，再用一个鸡蛋测试
* 一层楼要一次
* 二层楼要二次
* 三层楼要二次
* 四层楼要1+2次
* 五层楼要1+2次
* 六层楼要1+3次
* */
public class Blank {
public int superEggDrop(int K, int N) {
if(K == 1)
return N;
if(N == 1)
return N;
return superEggDrop(K - 1, N / 2) + 1;
}
}
实际结果比系统给出的结果有时候会大一点，改了各种参数，还是不太对，也不太明白，直到看讲解，有人说了一句，比如2个鸡蛋100次，二分法肯定不是最优解，那样要51次，我！！！！
所以鸡蛋的个数限制了最优解，换而言之，这题最优解并没有固定的方案，但一定存在，这不就是动态规划吗？！我对不起我的备注QAQ
动态规划：
- 确定状态：开数组，描述状态
- 确定最后一步
- 表达关系
暴力规划：
基础动态规划代码如下，时间复杂度O（KN2），空间复杂度O(KN）：
package test;
import static java.lang.Math.max;
import static java.lang.Math.min;
/**动态规划？
* 一个鸡蛋，要N次
* 零层楼要零次
* 一层楼要一次
* 二层楼要二次
* */
public class Blank {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K + 1][N + 1];
for(int i = 0; i < N + 1; i ++) {//初始化，一个鸡蛋，N层
dp[0][i] = 0;
dp[1][i] = i;
}
for(int i = 0; i < K + 1; i ++) {//初始化，一层，K个鸡蛋
dp[K][0] = 0;
dp[K][1] = 1;
}
for(int i = 2; i < K + 1; i ++) {//鸡蛋个数
for(int j = 2; j < N + 1; j ++) {//楼层数
dp[i][j] = max(dp[i - 1][1],dp[i][j - 1]) + 1;//鸡蛋碎了，i层之下；鸡蛋不碎，i层之上,默认在一楼扔
for(int k = 2; k <= j; k ++) {//从第k层扔
dp[i][j] = min(dp[i][j],max(dp[i - 1][k - 1],dp[i][j - k]) + 1);
}
}
}
return dp[K][N];
}
}
上面这种方法很好理解，但是复杂度高，很容易就超出时间限制。
降低复杂度
dp[i][j] = max(dp[i - 1][k - 1],dp[i][j - k]) + 1;
前者随着k增加变大，后者随着k增加变小；两者的最大值最小时，应该是交汇的点（图像如一个V字的最低点），于是逐层计算的地方可以改为使用二分法将复杂度降为logN，整体复杂度为O(KNlogN）
package test;
import static java.lang.Math.max;
import static java.lang.Math.min;
/**
* 动态规划？
* 一个鸡蛋，要N次
* 零层楼要零次
* 一层楼要一次
* 二层楼要二次
*/
public class Blank {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K + 1][N + 1];
for (int i = 1; i < K + 1; i++) {//鸡蛋个数
for (int j = 1; j < N + 1; j++) {//楼层数
if (i == 1)//初始化，一个鸡蛋，N层
dp[i][j] = j;
else if (j == 1)//初始化，一层，K个鸡蛋
dp[i][j] = 1;
else {
int left = 1;
int right = j;
while (left + 1 < right) {
int mid = (left + right) / 2;
int d1 = dp[i - 1][mid - 1];//增函数:鸡蛋碎了，i层之下；
int d2 = dp[i][j - mid];//减函数:鸡蛋不碎，i层之上,默认在一楼扔
if (d1 < d2) {
left = mid;
} else if (d1 > d2) {
right = mid;
} else
left = right = mid;
}
dp[i][j] = min(max(dp[i - 1][left - 1], dp[i][j - left]) + 1, max(dp[i - 1][right - 1], dp[i][j - right]) + 1);
}
}
}
return dp[K][N];
}
}
决策单调性
时间复杂度O(KN)，空间复杂度O(N)
这种做法有点是因为dp[K,N]的状态仅和状态A：dp[K-1,X-1]和B：dp[K,N-X]两个有关，我们可以考虑外层使用鸡蛋个数K作为循环条件，用一维数组dp[i]表示有i层时的最优解。
再假设x为最优解楼层，当K不变，N增加时，B是递增的，而B是不变的，所以x是单调递增的，这里可以减少复杂度。
import static java.lang.Math.max;
import static java.lang.Math.min;
class Solution {
public int superEggDrop(int K, int N) {
int[] dp = new int[N + 1];
int[] dpformer = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
dp[i] = i;//一个鸡蛋时需要的次数
dpformer[i] = i;
}
for (int i = 2; i < K + 1; i++) {//鸡蛋个数,此后刷新的dp[i]即dp[k][i]
//dp[i] = dp[N-x]（这一轮）和dp[x-1]（前一轮）中的最大值
int x = 1;//初始最优层
for (int j = 1; j < N + 1; j++) {//寻找有k个鸡蛋时最合适的层数
while (x <= j && dpformer[x - 1] < dp[j - x]) {
x++;
}
int temp = dp[j];
//此时已找到上下位置交换的那个点
dp[j] = 1 + min(dpformer[x - 1], dp[j - (x - 1)]);
dpformer[j] = temp;
}
}
return dp[N];
}
}
逆向推导
这是换一个角度考虑，若给定T步，K个鸡蛋，那么能能够测出来的楼层数最高是多少层，找到所有结果为N的中最小的那个T，就是我们要的答案。
时间复杂度是O(KN)，空间复杂O(KN)；
假设dp[T,K]为至少可以测出的最高层数：
初始条件为：dp[1,K] = 1;dp[T,1] = T
转移条件：假设在X层扔鸡蛋
- 鸡蛋碎了：dp[T,K] = N-X + dp[T-1,K-1]
- 鸡蛋不碎：dp[T,K] = X + dp[T-1,K];
“本次扔之后可能测出来的层数+本次扔之前已经测出来的层数”
那么在第t次的时候应该在哪层扔呢，即dp[t - 1][K - 1] + 1层扔，此时有两种情况：
鸡蛋碎了，那么我们能在t-1步内，用K-1个鸡蛋对楼下dp[t - 1][K - 1]层求解；鸡蛋不碎，那么我们排除了楼下的dp[t - 1][K - 1]层数，剩下还能对楼上的dp[t-1][K]层求解，所以是相加。
PS：上述两个情况，鸡蛋不碎才是不幸的情况，因为只要碎了一次，就可以求解任意高的情况（这楼以上都会碎），相当反直觉
代码如下：
package test;
import static java.lang.Math.max;
import static java.lang.Math.min;
/**
* 假设dp[T,K]为至少可以测出的最高层数：
* 转移条件：在dp[t - 1][k - 1] + 1层扔鸡蛋
* 1. 鸡蛋碎了：dp[T,K] = 这层下面可以有dp[t-1,k-1]层，保证可以测完//这种情况理论上可以测最高N层，因为大于这层楼的楼层数都能测
* 2. 鸡蛋不碎：dp[T,K] =这层上面可以有dp[t-1,k]层，保证可以测完;已经测了的楼层数为dp[t - 1][k - 1] + 1
* 扔之前已经测算的楼层数目加上扔之后还能算的数目
*/
public class Blank {
public int superEggDrop(int K, int N) {
int[][] dp = new int[N + 1][K + 1];
for (int i = 1; i < N + 1; i++) {//可以行动的次数，边界条件
for (int j = 1; j < K + 1; j++) {
if (i == 1) dp[1][j] = 1;//初始条件,一次只能测一层
else if (j == 1) dp[i][j] = i;//初始条件，一个鸡蛋只能测T层
else //状态转移条件
dp[i][j] = 1 + dp[i - 1][j - 1] + dp[i - 1][j];
if (dp[i][j] >= N) {
return i;
}
}
}
return N;//基本上不会return这个
}
}
PS：果然不能小看困难难度的题目，Markdown真好用啊
网友评论