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.

class Solution {
public:
    int memo[3][1001]; 
    int twoEggDrop(int n) { 
         return dfs(2, n);;
    }
    int dfs(int egg, int floor){
        if(floor == 1 || floor == 0 || egg == 1)
            return floor; 
        if(memo[egg][floor])
            return memo[egg][floor]; 
        int res = 2000;
        for(int i = 1; i <= floor; i++) {
            res = min(res, max(dfs(egg - 1, i - 1), dfs(egg, floor - i)) + 1);
        } 
        memo[egg][floor] = res;
        return res;
    }
};