力扣题解（鸡蛋掉落）
已解答
困难
相关标签
相关企业
给你 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;
else
l=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];
}
};原文地址：https://blog.csdn.net/yyssas/article/details/142929333
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！