力扣题解（鸡蛋掉落）

887. 鸡蛋掉落

已解答

困难

相关标签

相关企业

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

思路：

首先，该问题是一个动态递归的问题，且一维无法表示，因此需要二维。

f[i][j]表示一共i层楼，有j个鸡蛋的最小操作次数。

f[i][j]的值取决于选择的楼层k，k从1到i，对于一个确定的k，若鸡蛋碎了，则楼层范围变成k到i，一共i-k层楼，j-1个鸡蛋，就是f[i-k][j-1]，若鸡蛋没碎，则楼层变成k-1层，鸡蛋仍然是j个，就是f[k-1][j]，f[i][j]就是所有k取值的最小值，因此暴力做法就是三重循环，第一重表示总的楼层数，第二重是当前的鸡蛋数，第三重是选择丢鸡蛋的楼层，时间复杂度是O（N^2 *K），其中N表示楼层数，k表示鸡蛋总数，会超时。优化的地方是扔鸡蛋的楼层的选择。可以明显的发现，当扔鸡蛋的楼层变高的时候，f[k-1][j]是增大的，而f[i-k][j-1]是减小的，而要求的是同一个k对应的二者的最大值，因此只要找到交点附近的整数，就是解的取值，可以采用二分的思路。

对于二分，若交点刚好是整数，则最小的解就是当前的交点。否则，解是交点左右的两个整数取得的解，令l=1，r=n，当l+1<r不再成立的时候，l和r就是所要求的点。最小的解就是在这两个中的取得，时间复杂度变成了O（NlogN *K）。

class Solution {
public:map<int,int>hash;int superEggDrop(int k, int n) {return dp(k,n);}int dp(int k,int n){if(hash.count(n*100+k)){//}else{int ans=0;if(n==0)ans=0;else if(k==1)ans=n;else{int l=1,r=n;while(l+1<r){int mid=(l+r)/2;int t1=dp(k-1,mid-1);int t2=dp(k,n-mid);if(t1>t2)r=mid;else if(t1<t2)l=mid;elsel=r=mid;}ans=min(max(dp(k-1,l-1),dp(k,n-l)),max(dp(k-1,r-1),dp(k-1,n-r)))+1;}hash[n*100+k]=ans;}return hash[n*100+k];}
};