高楼扔鸡蛋

题目描述：面前有一栋楼从1到N共N层的楼，然后给你K个鸡蛋（K至少为1）。现在确定这栋楼存在楼层0<=F<=N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于F的楼层都会碎，低于F的楼层都不会碎）。现在问，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层F呢？

分析1：使用二分查找思路，从中间楼层进行尝试，实际上，如果不限制鸡蛋个数的话，二分思想显然可以得到最少尝试的次数，但问题是，现在给你了鸡蛋个数的限制K，直接使用二分思路就不行了。

原因：比如只给你1个鸡蛋，7层楼，你敢用二分吗？你直接去第4层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层F了。 

分析2：对于动态规划问题，我们需要考虑：【状态】+【选择】 

状态：当前拥有的鸡蛋数K和需要测试的楼层数N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。选择：就是选择去哪层楼扔鸡蛋。

我们选择在第i层楼扔鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎，所以状态转移就来了：

鸡蛋碎了：那么鸡蛋的个数K--，搜索的楼层区间应该从[1...N]变为[1...i-1]共i-1层楼；鸡蛋没碎：那么鸡蛋的个数K不变，搜索的楼层区间应该从[1...N]变为[i+1...N]共N-i层楼。

分析3：定义状态转移方程：dp[k][m]=n，当前有k个鸡蛋，可以尝试扔m次鸡蛋（m是一个允许的次数上界），这个状态下，最坏情况下最多能准确测试一栋n层的楼。

int supperEggDrop(int K,int N){ int m=0; while(dp[K][m]<N){ m++; //状态转移 } return m; }

状态转移：

无论在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测试楼下，没碎的话就测楼上；无论上楼还是下楼，总的楼层数=楼上的楼层数+楼下的楼层数+1（当前这层楼）

dp[k][m]=dp[k][m-1]+dp[k-1][m-1]+1

dp[k][m-1]就是楼上的楼层数，因为鸡蛋个数k不变，也就是鸡蛋没碎，扔鸡蛋次数m减一；dp[k-1][m-1]就是楼下的楼层数，因为鸡蛋个数k减一，也就是鸡蛋碎了，同时扔鸡蛋次数m减一。

int superEggDrop(int K,int N){ vector<vector<int>> dp(K+1,vector<int>(N+1)); int m=0; while(dp[K][m]<N){ m++; for(int k=1;k<=K;k++){ dp[k][m]=dp[k][m-1]+dp[k-1][m-1]+1; } } return m; }

分析4：定义状态转移：dp[m][k]=n，当前尝试次数为m，有k个鸡蛋，可以测试楼层n

dp[m][k]=dp[m-1][k]+dp[m-1][k-1]+1

降维：dp[k]=dp[k]+dp[k-1]+1

int superEggDrop(int K, int N) { vector<int> f(K+1); //f[m][k]=f[m-1][k]+f[m-1][k-1]+1 //f[m][k]：最少尝试m次，鸡蛋个数有k个，可以测试的楼层 //f[m-1][k]：鸡蛋没碎，尝试次数减一，鸡蛋个数还是m，可以测试楼上的层数 //f[m-1][k-1]：鸡蛋碎了，尝试次数减一，鸡蛋个数减一，可以测试楼下的层数 //f[k]=f[k]+f[k-1]+1 int m; for(m=0;f[K]<N;m++){ for(int i=K;i>=1;i--) f[i]+=f[i-1]+1; // } return m; }