题目地址: 887.鸡蛋掉落*
从简单的鸡蛋个数K=2，且楼层N=100开始分析：
2个鸡蛋时，第一个鸡蛋用来划分区间，第一个鸡蛋一旦碎掉，第二个鸡蛋只能在第一个鸡蛋划分出的最后一个区间内一层一层丢。例如可以将本题中的100层楼等距划分，分成10个10层楼，第一个鸡蛋丢10，20......100，假如第一个鸡蛋在30层碎了，说明强度在20-29之间，第二个鸡蛋就需要从21到29一层一层丢，即可确定鸡蛋的强度。容易计算，如果强度在第一个区间1-10，先丢10，然后丢1,2,3.....9，也就是强度在9层时，鸡蛋最多丢1+9=10次。如果在第二个区间，11-20，先10没碎，然后20碎了，然后丢21,22,23......29，鸡蛋最多丢2+9=11次。所以当楼层刚好在99层时，本算法需要10+9=19次。题目的要求是无论强度是多少，要输出确定这个强度的最小移动步数。也就是说使用等分算法会输出19，显然是无法通过这道题目的。
仔细看不难发现，上面算法的很大的问题在于需要的次数在各个区间依次增大，最后的返回值只由最高区间决定。因此是否可以将底下的区间多放一些楼层，上面的区间少放一些楼层，从而让所有的区间的最坏情况达到一致？在这里给出一个等差数列，楼层从下往上是a,a-1,a-2......1，如此总的楼层可以算出是（a+1）a/2>N=100,也就是a>=14，这里a取14。也就是划分楼层从下往上分别为：14，13，12，11，10，9，8，7，6，5，4，1。和上面一样验算可以得到第一区间最多需要14次，第二区间最多也是14次，除了最上层区间小于14次其余区间都是14次。该方法成功的分散了最上层的“压力”，最后返回14也就是K=2，N=100时的正确的解。
是否能将上面这种等差数列的思想进行推广到一般（K>=2，N>=2）呢：
先以K=3，N=1000为例：
很容易想到先用第一个鸡蛋将其划分大区间，再剩下两个鸡蛋测大区间内部。如果用第一个鸡蛋将1000层划分成10个100层，显然对于每一个100层的大区间，用2个鸡蛋测他们的次数都是一样的。那就会导致和上面一样的问题，也就是下面区间需要的次数比上面少1次，最上层区间决定了最坏的情况。
那么是否可以像上面一样，将大区间等差排列让2个鸡蛋在大区间内部测量的步数逐层递减呢？我们已经知道了2个鸡蛋测量100层需要19步，那2个球测量99层需要多少步我们却暂时不得而知，也就说我们不知道100减去多少层，可以让2个球18步就给测出来。
只有2个鸡蛋的时候，我们能够确定1个鸡蛋m步就是能测m层，所以用第一个鸡蛋划分的区间楼层是一个等差数列；而三个鸡蛋的时候，我们不能确定2个鸡蛋m步能测多少层，第一个鸡蛋所划分的区间必然是一个递减的区间，但是具体递减多少却不得而知。
也就是说3个鸡蛋时，第一个鸡蛋划分区间需要先知道一个问题：2个球m步最多能测多少层。但是如果知道了K个球m步最多能测多少层，就没有必要再划分了，因为只要固定K的值，增大m，求得的值也就是能够测量的最大层数只要大于了N，返回m就行了。因此就有了下面这种解法一。
解法一：K个鸡蛋m步最多能测多少层
F(k,m)代表k个鸡蛋能测量的最大层数，显然k=1时，只有一个鸡蛋，只能一层一层扔，即F(1,m)=m，如果只能走一步，无论k是多少，只要有一个鸡蛋，最多就能测1层，也就是F(k,1)=1。对于一般性的F(k,m)，如果一个鸡蛋在某一楼层碎了，那么应该在该楼层下面继续测，此时鸡蛋k-1，步数m-1，最多可以测F(k-1,m-1)层楼；如果鸡蛋在该层没碎，那么应该在该楼层上面继续测，此时鸡蛋k不变，步数m-1，最多可以测F(k,m-1)层楼。由此得F(k,m)=F(k-1,m-1)+F(k,m-1)+1。
综上，递推方程：F(k,m)=F(k-1,m-1)+F(k,m-1)+1 边界条件：F(k,1)=1、F(1,m)=m
class Solution {
public int superEggDrop(int K, int N) {
if(K<=0 || N<=0) return 0;//错误输入
for(int i=1;i<=N;i++){
if(func(K,i)>=N) return i;//k个鸡蛋，i步能测的楼层大于N了就直接返回步数
}
return 0;//到不了这里,但是函数必须写返回值
}
//递归计算k个鸡蛋，m步，能测多少层楼
public int func(int k,int m){
//边界条件
if(k==1) return m;
else if(m==1) return 1;
return func(k-1,m-1)+func(k,m-1)+1;
}
}
将代码复制进leetcode可以通过，但是在时间上只打败了80%的人，仔细分析不难发现，该算法没有保存中间结果，递归过程中有很多的重复计算。但是要想用二维数组来存储中间结果又会遇到困难，不妨大家可以尝试一下，因为不知道该申请多长的二维数组。
在网上找到了一个很巧妙的方法，仔细分析递推方程：F(k,m)=F(k-1,m-1)+F(k,m-1)+1 ，可以看到左侧都是m，右侧都是m-1。可以只使用一列存储数据，K从大到小进行更新。这样能够在时间上打败100%。时间复杂度是O(KlogN)，空间复杂度O(K)，是网上当前所有解法中的最优解法。
class Solution {
public int superEggDrop(int K, int N) {
int[] dp = new int[K+1]; //int型会自动初始化为0
int m = 0;
while (dp[K]<N){
m++;
for (int i = K; i >= 1; i--){
dp[i] = dp[i] + dp[i-1] +1;
}
}
return m;
}
}
解法二：普通动态规划
假设F(k,n)代表k个鸡蛋测n层楼最少需要的次数。如果在某一个层t层摔碎了，那么需要用k-1个鸡蛋在t层下的t-1层找，次数是F(k-1,t-1)；如果在t层没碎，那需要用k个鸡蛋在t层上的n-t层找，次数是F(k,n-t)。由此总的次数F(k,n)=Max(F(k-1,t-1),F(k,n-t))+1。t从1层遍历到N层，得到的F(k,n)的最小值就是要求的值。
递推方程：F(k,n)=Max(F(k-1,t-1),F(k,n-t))+1 边界条件：F(k,1)=1、F(1,N)=N
此方法时间复杂度是O(K*N^2)，空间复杂度O(KN)
class Solution {
public int superEggDrop(int K, int N) {
if(K<=0 || N<=0) return 0;
int[][] F = new int[K+1][N+1];//0行0列不用
for(int i=1;i<=N;i++){//F[1][N]=N
F[1][i]=i;
}
for(int i=1;i<=K;i++){//F[k][1]=1
F[i][1]=1;
}
for(int i=2;i<=K;i++){
for(int j=2;j<=N;j++){
int min=N;
for(int t=1;t<=j;t++){
min=Math.min(min,Math.max(F[i-1][t-1],F[i][j-t])+1);
}
F[i][j]=min;
}
}
return F[K][N];
}
}
这个代码虽然没有问题能够求出正确的结果，但是时间复杂度实在是太高了，以至于复制到leetcode里会因为超时而无法通过。那么怎么降低时间复杂度呢。可以看到t的遍历过程，是从底向上全部遍历了一遍，这里其实可以不必如此，因为如果k不变，n增大了，这个用来划分的最佳的t一定是增大的。所以有如下代码，能够将时间复杂度降低到O(KN)，空间复杂度依旧是O(KN)。该在leetcode上打败了35.7%的人。
class Solution {
public int superEggDrop(int K, int N) {
if(K<=0 || N<=0) return 0;
int[][] F = new int[K+1][N+1];//0行0列不用
for(int i=1;i<=N;i++){//F[1][N]=N
F[1][i]=i;
}
for(int i=1;i<=K;i++){//F[k][1]=1
F[i][1]=1;
}
for(int i=2;i<=K;i++){
int t=1;
for(int j=2;j<=N;j++){
while(t<N && F[i-1][t-1]<F[i][j-t]) t++;
F[i][j]=F[i-1][t-1]+1;
}
}
return F[K][N];
}
}
