一、暴力递归法
首先,我们来看扔鸡蛋这个事儿本身,假设在N
层的高楼中有K
个鸡蛋,这个时候我们在n
层扔了一个鸡蛋,那么这一次动作,把整个高楼其实就分成了两部分,一部分是1楼到n
楼,这是一个层高为n
的新楼,我们暂时叫它一号楼;另一部分是n+1
到N
楼,这是一栋新产生的层高为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; }