鸡蛋掉落问题

一、暴力递归法

首先,我们来看扔鸡蛋这个事儿本身,假设在N层的高楼中有K个鸡蛋,这个时候我们在n层扔了一个鸡蛋,那么这一次动作,把整个高楼其实就分成了两部分,一部分是1楼到n楼,这是一个层高为n的新楼,我们暂时叫它一号楼;另一部分是n+1N楼,这是一栋新产生的层高为N-(n+1)+1=N-n的新楼,我们叫他二号楼。

然后,我们来看刚扔下去的鸡蛋,如果它碎了,说明楼层太高(起码高于F),那么F应该是在一号楼,那么我们就带着剩下的K-1个鸡蛋去一号楼继续,当我们站在一号楼的某一层的时候,其实和最开始是一样的(递归的信号)。如果鸡蛋没碎,说明楼层不够高(低于F),此时我们要去二号楼,但是这里有一点点需要注意的,就是我们在二号楼的某一层的时候,其实该层在原始的楼里是要比当前楼层高n层的,其他同理。
最后,因为我们是要找无论 F 的初始值如何的条件下的查找次数,所以我们要在一号楼和二号楼各自的查找次数中选择那个最大的值,用计算机语言描述整个过程,就是

searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) )

public int superEggDrop(int K, int N) {
    return recursive(K, N);
}

public int recursive(int K, int N) {
    if (N < 2 || K == 1)
        return N;
    int min = N;
    for (int i = 1; i <= N; i++) {
        min = Math.min(min, 1+Math.max(recursive(K - 1, i - 1), recursive(K, N - i)));
    }
    return min;
}

二、DP法

public int superEggDrop(int K, int N) {
    int[] dp=new int[K+1];
    int step=0;
    for(;dp[K]<N;step++){
        for(int i=K;i>0;i--){
            dp[i]+=(1+dp[i-1]);
        }
    }
    return step;
}