【每日算法Day 59】高楼扔鸡蛋问题
# LeetCode 887. 鸡蛋掉落 (opens new window)
# 题目描述
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
# 示例
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
2
3
4
5
6
7
# 解题思路
本题的题目描述比较复杂，其核心是在最坏情况下（即F位于你采用的搜索策略的最坏情况）下要找到F需要扔多少次鸡蛋。如果只有一个鸡蛋，那么显然只能从下往上线性搜索否则鸡蛋碎了就不能再次搜索了，这时最坏情况是F=N。如果有超过Log(2,N)个鸡蛋，那么可以采用二分查找的方法，这时最坏情况是Log(2,N)向上取整，即一直找到二分查找的搜索空间收缩为1为止。
但现在鸡蛋的数量K有限制，所以可以尝试用动态规划的思想去解决该问题。
首先我们考虑该问题的状态是什么：当前有的鸡蛋数量i和剩余要搜索的楼层数j；
然后当前状态的选择是什么：如果当前我们在1~j的某一楼层x扔鸡蛋的测试结果，可以选择继续搜索1~x的楼层（鸡蛋碎了）还是x~j的楼层（鸡蛋没碎），这时为保证在最坏情况下能确定F，要选择这两种选择中移动次数最多的。同时根据测试楼层x的不同也就是我们的搜索策略的不同，该最差情况下的移动次数也会有一个最小值。这里的选择就是在1~j中的哪一层扔鸡蛋。
状态转移：如果鸡蛋碎了，选择继续搜索1~x的楼层，鸡蛋数减一；如果鸡蛋没碎，选择搜索x~j的楼层。两种选择之后移动次数都加一。
最后我们来看base case：当楼层为0时显然搜索次数为0，当楼层为1时搜索次数为1。当只有一个鸡蛋时，只能从下往上线性搜索，最坏搜索次数为楼层数。
public int superEggDrop(int K, int N) {
//dp[i][j]表示有i个鸡蛋要找j层楼
int[][]dp = new int[K + 1][N + 1];
for (int i = 0; i <= K; i++) {
Arrays.fill(dp[i],10000);
}
for (int j = 1; j <= N; j++) {
dp[1][j] = j;
}
for (int i = 1; i <= K; i++) {
dp[i][1] = 1;
dp[i][0] = 0;
}
for (int i = 2; i <= K; i++) {
for (int j = 2; j <= N; j++) {
for (int x = 1; x <=j ; x++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][j - x], dp[i - 1][x - 1])+1);
}
}
}
return dp[K][N];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
一共有 O(K*N)个状态，对于每个状态枚举扔鸡蛋的楼层 X，需要 O(N) 的时间，所以总时间复杂度是为 O(K*N^2)。