题目
你将获得 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 是多少。
提示：
1 <= K <= 100
1 <= N <= 10000
题解
看到题目，第一时间想到了用二分查找的思路来解题，碎了往下走，没有碎往上走。但是看题目会发现还有一个数据K没有利用上，扔鸡蛋还会受到鸡蛋数量的约束，比如有1个鸡蛋，7层楼，二分查找从第四层开始扔，如果鸡蛋碎了，就无法继续进行测试了。因此仅仅使用二分查找思路是不可取的。
此题采用动态规划的方法，同样的首先分析【状态】，即你目前有的鸡蛋数量，和所在的楼层数，其次分析【选择】，即下一次在几楼扔。
设我们在第i层扔出了鸡蛋，根据题意
如果鸡蛋碎了：则k--,下一次扔的楼层应该在[1,i-1]之间
如果鸡蛋没碎：则k不变，下一次扔的楼层在[i+1,N]之间，
因此我们在i层有k个鸡蛋必须移动的部署为ans_i = max(dp(k-1,i-1),dp(k,i+1)) + 1
N层楼需要的最少步数为min(ans_1,ans_2,...,ans_n),代码描述为：
int dp(int k,int n){
int ans;
for(int i = 0;i < n;i++){
ans = min(ans,max(dp(k-1,i-1),dp(k,n-i) + 1);
}
return ans;
}
base case :
if(k == 1) return n;
if(n == 0) return 0;
代码
class Solution {
public:
int superEggDrop(int K, int N) {
if(K == 0 || N == 0) return 0;
if(K == 1) return N;
if(N == 1) return 1;
int minDrop = N + 1;
for(int x = 1; x <= N; x ++){
minDrop = min(minDrop, max(superEggDrop(K, N-x), superEggDrop(K-1, x-1)) + 1);
}
return minDrop;
}
};
此算法时间复杂度为指数级，因此我们考虑采用带有备忘录的动态规划算法来进行优化，具体操作为用一个数组存放K,N状态下需要的步数，每次dp时先查询该状态是否已经存在，如过存在则直接返回该值值，由于题目中1<=k<=100,我们可以用N * 100 + k来表示K,N状态的序号，每次返回前将步书保存在unordered_map(内部为hash表比map的查询速度快)中。
优化1：
class Solution {
unordered_map<int,int> t;
public:
int superEggDrop(int K, int N) {
if(K == 0 || N == 0) return 0;
if(K == 1) return N;
if(N == 1) return 1;
if(t.find(N*100+K) == t.end()){
int ans = N + 1;
for(int x = 1; x <= N; x ++){
ans = min(ans, max(superEggDrop(K, N-x), superEggDrop(K-1, x-1)) + 1);
}
t[N*100+K] = ans;
}
return t[N*100+K];
}
};
然而通过备忘录之后的时间复杂度仍为O(KNN),仍然无法满足，此刻回忆我们最初想到的二分查找思路，我们通过二分查找的思路，可以将时间复杂度降至O(KNlogN),具体操作为：
先前我们的搜索方式都是线性搜索，观察dp(K-1,x-1)和dp(K,N-x)，当K一定时随着x的增大前者单调递增，后者单调递减。因此dp(K,N) = MIN(MAX(dp(K-1,x-1),dp(K,N-x)) + 1)可以看作求两个函数交点，这个过程可以通过二分查找来进行优化
class Solution {
unordered_map<int,int> t;
public:
int superEggDrop(int K, int N) {
if(K == 0 || N == 0) return 0;
if(K == 1) return N;
if(N == 1) return 1;
if(t.find(N*100+K) == t.end()){
int ans = N + 1;
int l = 1,h = N;
while(l <= h){
int mid = (l + h) / 2;
int broken = superEggDrop(K-1,mid-1);
int not_broken = superEggDrop(K,N-mid);
if(broken > not_broken){
h = mid - 1;
ans = min(ans,broken + 1);
}
else{
l = mid + 1;
ans = min(ans, not_broken + 1);
}
}
t[N*100+K] = ans;
}
return t[N*100+K];
}
};
此时算法搜索的时间复杂度已经优化为O(logN)，总体时间复杂度优化为O(KNlogN)，可满足题目要求
网友评论