1884. 鸡蛋掉落-两枚鸡蛋
已解答
中等
相关标签
相关企业
提示
给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。
每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
思路：
首先，从越高的楼往下丢，一定要比从低的楼往下丢要耗费更多比较次数，且从高的楼往下丢的结果依赖于从低的楼向下丢，因此是动态递归。
f[i]表示从一共i层楼丢的最小操作次数，对于f[i]的计算，其结果取决于第一枚鸡蛋从哪里丢，即从第一层楼到第i-1层楼开始丢，规定丢的楼层是k，则对于从k层楼丢有两种情况，鸡蛋碎了和没碎，若碎了，则不会碎的楼一定是在第1层到第k-1层，由于此时只剩下一枚鸡蛋，要从第一层开始一层层测试，因此最多还需要k-1次。若没有碎，则一定是在第k层到第i层之间，就是f[i-k]。此处之所以还可以用f来表示，是因为不同楼层实际上没有任何差别，即从1到k和从k到2k-1之间，求最下操作次数的结果没有差别，所以可以复用f函数。由于是能得到确切结果，因此要碎和没碎里面的最大值，又要最小的操作次数，所以是对不同取值k的最小值。
class Solution {
public:int twoEggDrop(int n) {int f[10010];memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=n;i++)for(int t=1;t<=i;t++)f[i]=min(f[i],max(f[i-t],t-1)+1);return f[n];}
};
)
