题目：
给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。
每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。
示例 2：
输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。
提示：
1 <= n <= 1000
思路：
一、寻找子问题
假设 n=10。
如果第一枚鸡蛋在 4 楼扔下，分类讨论：
如果鸡蛋碎了，那么接下来只能依次在 1,2,3 楼扔第二枚鸡蛋，最坏情况下，总共要操作 1+3=4 次。
如果鸡蛋没碎，那么接下来可以在 5 到 10 楼中继续扔第一枚鸡蛋，这等价于在一栋有 10−4=6 层楼的建筑中扔鸡蛋的子问题。这个子问题的结果加上 1，就是原问题 n=10 的答案。
这两种情况取最大值，因为在扔之前，我们不知道鸡蛋是否会碎。为了保证无论在何种情况下，我们都可以确定 f 的值，所以要取最大值。
一般地，可以枚举第一枚鸡蛋在 1,2,3,⋯,10 楼扔下，分别计算每种情况需要操作多少次，取其中最小值，作为最终的答案。
比如第一枚鸡蛋在 4 楼扔下，到最终确定 f，需要操作 4 次。而第一枚鸡蛋在 2 楼扔下，到最终确定 f，需要操作 5 次。那么相比在 2 楼扔，肯定是在 4 楼扔更优。
由于我们会遇到和原问题相似的、规模更小的子问题，所以可以用递归解决。
二、状态定义与状态转移方程
根据上面的讨论，定义状态为 dfs(i)，表示在一栋有 i 层楼的建筑中扔鸡蛋，无论 f 等于多少，我们都能确定 f 的最小操作次数。
枚举第一枚鸡蛋在 j=1,2,3,⋯,i 楼扔下，分类讨论：
如果鸡蛋碎了，那么接下来只能依次在 1,2,3,j−1 楼扔第二枚鸡蛋，最坏情况下，总共要操作 1+(j−1)=j 次。
如果鸡蛋没碎，那么接下来可以在 j+1 到 i 楼中继续扔第一枚鸡蛋，这等价于在一栋有 i−j 层楼的建筑中扔鸡蛋的子问题，即 dfs(i−j)，将其加一即为总操作次数。
这两种情况取最大值，即为在第 j 楼扔下第一枚鸡蛋，到最终确定 f，所需要的最小操作次数，即 max(j, dfs(i−j) + 1)
对 j=1,2,3,⋯,i 的上式取最小值，得 dfs(i)= min (max(j, dfs(i−j)+1))
递归边界：dfs(0)=0。此时 f 一定等于 0，无需扔鸡蛋。
递归入口：dfs(n)，也就是答案。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1，但本题除了 dfs(0)，其余 dfs(i) 都是正数，所以初始化成 0 也可以。
代码：
int memo[1001];
class Solution {
public:
int twoEggDrop(int n) {
if (n == 0) {
return 0;
}
int& res = memo[n]; // 注意这里是引用
if (res) { // 之前计算过
return res;
}
res = INT_MAX;
for (int j = 1; j <= n; j++) {
res = min(res, max(j, twoEggDrop(n - j) + 1));
}
return res;
}
};