力扣 1884.Egg Drop Two Egg（两个鸡蛋掉落） - 输入： n = 100 输出： 1414 解说 最佳策略是 - 从 9 楼扔下第一个鸡蛋。如果蛋碎了，那么 f 在 0 和 8 之间。从第 1 层扔第 2 个鸡蛋，然后每扔 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=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 楼扔更优。

由于我们会遇到和原问题相似的、规模更小的子问题，所以可以用递归解决。