力扣1884.鸡蛋掉落 两枚鸡蛋

给你 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 。

很有意思的一道题

方法一：动态规划

一、寻找子问题
假设 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，所需要的最小操作次数，即​

递归边界：dfs(0)=0。此时 f 一定等于 0，无需扔鸡蛋。

递归入口：dfs(n)，也就是答案。

三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1，但本题除了 dfs(0)，其余 dfs(i) 都是正数，所以初始化成 0 也可以。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

class Solution:
    @cache
    def twoEggDrop(self, n: int) -> int:
        if n == 0:
            return 0
        return min(max(j, self.twoEggDrop(n - j) + 1) for j in range(1, n + 1))

f = [0] * 1001
for i in range(1, len(f)):
    f[i] = min(max(j, f[i - j] + 1) for j in range(1, i + 1))

class Solution:
    def twoEggDrop(self, n: int) -> int:
        return f[n]

。