题目：1884. 鸡蛋掉落-两枚鸡蛋
方法一：动态规划dp+递归dfs+记忆化搜索。时间复杂度0(n^2)。
C++版本：
class Solution {
public:
//状态sta[i]表示：i层找到f所需要的最小操作次数
int sta[1010];
int twoEggDrop(int n) {
//层数为0时，直接返回0
if(n==0) return 0;
//遍历过
if(sta[n]) return sta[n];
//初始化最大值
int mn=n;
//遍历可以选中哪层楼
for(int i=1;i<n;i++){
//如果在i层鸡蛋破碎了，那么我们只能从最低的层数开始往上。
//如果在i层鸡蛋完好，那f就在i+1~n层，这就类似于在1~n-i层之间寻找。
//这两种方案中选取最大需要的操作次数,再去和其他的i层进行比较。
mn=min(mn,max(i,twoEggDrop(n-i)+1));
}
//记忆化
return sta[n]=mn;
}
};
JAVA版本：
class Solution {
//状态sta[i]表示：i层找到f所需要的最小操作次数
private static final int[] sta=new int[1010];
public int twoEggDrop(int n) {
//层数为0时，直接返回0
if(n==0) return 0;
//遍历过
if(sta[n]>0) return sta[n];
//初始化最大值
int mn=n;
//遍历可以选中哪层楼
for(int i=1;i<n;i++){
//如果在i层鸡蛋破碎了，那么我们只能从最低的层数开始往上。
//如果在i层鸡蛋完好，那f就在i+1~n层，这就类似于在1~n-i层之间寻找。
//这两种方案中选取最大需要的操作次数,再去和其他的i层进行比较。
mn=Math.min(mn,Math.max(i,twoEggDrop(n-i)+1));
}
//记忆化
return sta[n]=mn;
}
}
方法二：动态规划dp+递推。时间复杂度为0(n^2)。
C++版本：
class Solution {
public:
int twoEggDrop(int n) {
//状态f[i]表示：i层找到f所需要的最小操作次数
vector<int> f(n+1,0);
for(int i=1;i<=n;i++){
//初始化最大值
f[i]=i;
//遍历可以选中哪层楼
for(int j=1;j<i;j++){
//如果在j层鸡蛋破碎了，那么我们只能从最低的层数开始往上。
//如果在j层鸡蛋完好，那f就在j+1~n层，这就类似于在1~n-j层之间寻找。
//这两种方案中选取最大需要的操作次数,再去和其他的j层进行比较。
f[i]=min(f[i],max(j,f[i-j]+1));
}
}
return f[n];
}
};
JAVA版本：
class Solution {
private static final int[] f=new int[1010];
public int twoEggDrop(int n) {
for(int i=1;i<=n;i++){
f[i]=i;
for(int j=1;j<i;j++){
f[i]=Math.min(f[i],Math.max(j,f[i-j]+1));
}
}
return f[n];
}
}
方法三：数学推导。
假设有x次操作次数，求n最大可以是多少。
第一次选最多只能选第x层：如果碎了，就可以从1开始往上。
如果没碎，第二次选最多只能选第x-1层：如果碎了，就可以从x+1开始往上。
…
直到最后最多只能选第1层:如果碎了，下一层就是答案；没碎，当前就是答案。
x+(x-1)+…+1>=n，即x^2+x-2n>=0。解方程，答案就是(sqrt(8n+1)-1)/2
C++版本：
class Solution {
public:
int twoEggDrop(int n) {
return ceil((sqrt(8*n+1)-1)/2);
}
};
JAVA版本：
class Solution {
public int twoEggDrop(int n) {
return (int)Math.ceil((Math.sqrt(8*n)-1)/2);
}
}