Problem:
You are given K eggs, and you have access to a building with N floors from 1 to N.
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
Example 1:
Input: K = 1, N = 2Output: 2Explanation: Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.If it didn't break, then we know with certainty F = 2.Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6Output: 3
Example 3:
Input: K = 3, N = 14Output: 4
Note:
1 <= K <= 1001 <= N <= 10000
Solution:
说道扔鸡蛋问题，就不得不提一下那个经典的dp问题。给m个鸡蛋尝试n次，最坏情况下可以在多少楼层内确定会让鸡蛋破裂的最低层数。
对于这道题，我们可以创建一个二维数组dp，dp[i][j]表示用i个鸡蛋尝试j次可以确定的最高楼层数。这个最高楼层可以由两部分组成，假设我们在x楼扔下一个鸡蛋，它可能会破也可能不会破，如果鸡蛋破了，那么我们需要用剩下的i-1个鸡蛋和就-1次机会在x楼之下寻找这个最高楼层，即dp[i-1][j-1]，若鸡蛋破了，则我们需要在x+1层之上用i个鸡蛋尝试j-1次找到那个最高楼层，即dp[i][j-1]，因此可以得到状态转移方程：dp[i][j] = dp[i-1][j-1]+1+dp[i][j-1]，对于i=1，dp[1][i] = i。代码部分如下：
1 class Solution { 2 public: 3 int superEggDrop(int K, int N) { 4 vector > dp(K+1,vector (N+1,0)); 5 for(int j = 0;j <= N;++j) 6 dp[1][j] = j; 7 for(int i = 2;i <= K;++i){ 8 for(int j = 1;j <= N;++j){ 9 dp[i][j] = dp[i-1][j-1]+1+dp[i][j-1];10 }11 }12 return dp[K][N];13 }14 };
现在来看这道题有什么不同呢，现在他告诉我们最高楼层，要我们找到最小的尝试次数，即告诉我们i和dp[i][j]要我们计算j的值。和上面那题的思路类似，我们令x为测试的楼层，在这一楼层扔鸡蛋有两种情况，如果蛋碎了，则我们需要在x-1层里用i-1个鸡蛋找到最小的尝试次数，如果蛋没碎，则要在x+1到j层用i个鸡蛋找到最小尝试次数，所以max（dp[i-1][x],dp[i][j-x]）即在x层扔下第一个鸡蛋的情况下，用i个鸡蛋在j层内的最小尝试次数。所以，我们需要在0-j层内找到合适的x，使得这个最小尝试次数最少，所以这就成了一个极小化极大值的问题。在这里其实我们可以观察到dp[i-1][x]是递增的，而dp[i][j-x]是递减的，所以我们在0-j内遍历x，当dp[i-1][x] == dp[i][j-x]时，可以断定此时的x即第一个鸡蛋应该扔的楼层，所以dp[i][j]就等于dp[i-1][x]+1。
对于这个解法，其时间复杂度为O(kN2)，我们可以观察到在确定x的过程中，我们通过遍历的方法寻找x，在这个地方我们其实可以通过二分法进行优化，将时间复杂度降低为O（kN*logN）。（虽然通过二分法时间复杂度降低了，但程序的运行时间却增加了，所以算法复杂度和程序运行时间真是没必然联系啊）
由于这道题的状态转移方程只需要i-1层的数据，其空间复杂度也可以降低为O(N)，感兴趣的读者可以继续优化算法。
Code:
1 class Solution { 2 public: 3 int superEggDrop(int K, int N) { 4 vector > dp(K+1,vector (N+1,0)); 5 for(int j = 0;j <= N;++j) 6 dp[1][j] = j; 7 for(int i = 2;i <= K;++i){ 8 int x = 1; 9 for(int j = 1;j <= N;++j){10 while(x < j && dp[i][j-x] > dp[i-1][x])11 x++;12 dp[i][j] = 1+dp[i][j-x];13 }14 }15 return dp[K][N];16 }17 };
1 class Solution { 2 public: 3 int superEggDrop(int K, int N) { 4 vector > dp(K+1,vector (N+1,0)); 5 for(int j = 0;j <= N;++j) 6 dp[1][j] = j; 7 for(int i = 2;i <= K;++i){ 8 for(int j = 1;j <= N;++j){ 9 int start = 1;10 int end = j;11 while(start < end){12 int pivot = start+(end-start)/2;13 if(dp[i][j-pivot] > dp[i-1][pivot])14 start = pivot+1;15 else16 end = pivot;17 }18 dp[i][j] = 1+dp[i][j-start];19 }20 }21 return dp[K][N];22 }23 };