Egg Drop With 2 Eggs and N Floors

给两个鸡蛋和n层楼, 已知一个鸡蛋从x层楼掉下去不会碎,但是从x+1层就会碎 求最少多少次扔鸡蛋可以知道x是多少.

典型的dp题, 可以用一个memo存当前的状态: 首先, 如果只有一个鸡蛋, 那么测n层楼需要测n次. 这里不用binary search, 因为我们的求的是最少多少次扔鸡蛋, 而binary search不一定能找到正确的解, 最坏情况我们还是要扔n次. 转移方程中, 两个状态是:1. 扔了没有碎, x肯定在当前i floor的上边: drop(egg, floor - i), 2. 扔了碎了, x肯定在当前i floor的下边 drop(egg - 1, i - 1). 因为同样数量的move下,我们需要找的是两个解中, 最”高”的一层所以取两个状态的max. 然后和当前的所有状态中的每个状态取min.