887. 鸡蛋掉落
· 约 2 分钟阅读 · – 次阅读
leetcode
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 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个鸡蛋，只能从低到高一层楼一层楼的遍历
- 有2个鸡蛋，100层楼，可以考虑分10层，这样最大需要19次，也可以考虑让第一个鸡蛋和第二个鸡蛋最大尝试次数之和均匀一点，
- 有k个鸡蛋，n层楼，dp[k, n]。选择任意扔鸡蛋的位置为x，则有两种情况且：
- 鸡蛋碎了，则消耗一个鸡蛋，答案在x层下方的x-1楼层中。t1 = dp[k-1, x-1]
- 鸡蛋没碎，则消耗0个鸡蛋，答案在x层上方剩下的n-x楼层中。t2 = dp[k, n-x]
接下来就是寻找x的位置，然后计算每个x的取值情况下的最小值。
关于x的函数t1和t2, t1单调递增，t2单调递减，二者分段函数的最小值在交点处，考虑离散函数特点，选交点左右两个数。
class Solution {
unordered_map<int, int> memo;
int dp(int k, int n){
if (memo.find(n*100+k) == memo.end()){
int ans;
if (k == 1){
ans = n;
}else if (n <= 1){
ans = n;
}else{
int low = 1, high = n;
while (low + 1 < high){
int mid = (low+high)/2;
int t1 = dp(k-1, mid-1);
int t2 = dp(k, n-mid);
if (t1 < t2){
low = mid;
}else if(t1 > t2){
high = mid;
}else{
low = high = mid;
}
}
// cout << k << " " << n << endl;
// cout << "low-high:" << low << " " << high << endl;
// 抛鸡蛋的最佳点在low或high中之一
ans = 1 + min(max(dp(k-1, low-1), dp(k, n-low)), max(dp(k-1, high-1), dp(k, n-high)));
}
memo[n*100+k] = ans;
}
return memo[n*100+k];
}
public:
int superEggDrop(int k, int n) {
return dp(k, n);
}
};