用2个鸡蛋从100层楼层里寻找扔下鸡蛋不碎最高楼层的最小尝试次数

如果第一次扔鸡蛋没碎，第二次我们需要从x (x-1)层扔（因为总尝试次数，我们已经用了一次，所以需x-1），如果此时鸡蛋碎了，我们需要从x 1到x (x-1)-1逐级往上扔，最坏情况下次数为(x (x-1)-1)-(x 1) 1 2=x；

如果第二次鸡蛋没碎，第三次需从x (x-1) (x-2)层扔，如果此时鸡蛋碎了，最坏情况下次数为(x (x-1) (x-2)-1)-(x (x-1) 1) 1 3=x；

.....

以此类推，最坏情况下覆盖所有楼层，我们需要x (x-1) (x-2) ... 2 1=x(x 1)/2

之前，我们在思考在已知最优策略找最少次数，

现在需要换个角度，我们能否用已知最少尝试次数去覆盖所有楼层。

由此，我们可以得到一个方程式：

x(x 1)/2 >= 100

解方程式得x>=13.65，即最少尝试次数为14。

上面的题目，可以拓展为用N个鸡蛋从K层高的楼层里寻找扔下鸡蛋不碎最高楼层的最小尝试次数。

刚好就和LeetCode第887题super egg drop一样，解法主要有：

1. 递归，简单暴力，容易理解，但速度最慢；
2. 动态规划DP，在N和K的数值不是很大时，速度良好；
3. 二分查找与递归相结合，速度最快；

在LeetCode有三个示例用于说明极端情形下的最小尝试次数f，如：

1. K=1, N=2，则f=2；
2. K=2, N=6，则f=3；
3. K=3, N=14，则f=4；

看到这三个示例，相信很多人的第一反应也是递归。

假设你有n个鸡蛋去测试h个连续的楼层，接着你从第i层扔下了一个鸡蛋，则存在两种可能：

1. 如果鸡蛋碎了，问题就演变成你有n-1个鸡蛋去测试i-1个连续的楼层；
2. 2如果鸡蛋没碎，问题就演变成你有n个鸡蛋去测试h-i个连续的楼层；

按照此逻辑，我们可以定义函数F(n,h)用于计算使用最优策略用n个鸡蛋从h层高的楼层里寻找扔下鸡蛋不碎最高楼层的最小尝试次数，则有：

F(n,h) = 1 min(max(F(n-1,i-1),F(n,h-i)) (1=<i<=h)

递归在以下极端情况下结束：

1. 如果只有一个鸡蛋，你需从1开始扔，总次数为h；
2. 如果建筑物只有一层，无论你有多少个鸡蛋，总次数为1；

i从1到h重复上述过程，去最小次数即可。递归实现算法时间复杂度为O(n*2^n),空间为O(1)，代码实现如下：

public class SuperEggDrop { public int superDrop(int n,int h) { if(n == 1) return h; if(n == 0) return 0; if(h == 1) return 1; int min = Integer.MAX_VALUE; for(int start=1;start <= h;start ) { min = Math.min(min,(1 Math.max(superDrop(n-1,start-1),superDrop(n,h-start)))); } return min; } } 动态规划DP

上面递归解法，100层时单机已经跑不出来了，可见速度真的很慢。

递归转动态规划，其实就是用空间换时间，将子问题的计算结构先保存起来，避免重复计算。

我们可以用一个二维数组drops[n][h]，代表用n个鸡蛋查找h层楼层的最小尝试次数，

则drops[1][h]=h, drops[0][h]=0，drops[n][1]=1，依次将drops赋值即可。

代码实现如下：

public class SuperEggDrop { public int superDrop2(int n,int h) { int[][] drops = new int[n 1][h 1]; for(int i=0;i<=h;i ) drops[1][i] = i; for(int i=0;i<=h;i ) drops[0][i] = 0; for(int i=0;i<=n;i ) drops[i][1] = 1; int min = Integer.MAX_VALUE; for(int i=2;i<=n;i ) { for(int j=1;j<=h;j ) { min = Integer.MAX_VALUE; for(int x=1;x<=j;x ) { min = Math.min(min,1 Math.max(drops[i][j-x],drops[i-1][x-1])); } drops[i][j] = min; } } return drops[n][h]; } } DP与二分查找结合

我们再来观察等式右边max(F(n-1,i-1),F(n,h-i)，

F(n-1,i-1)是随i递增而线性递增，

F(n,h-i)是随i递增而线性递减，他们有可能在i的某个中间值重合。

两者取最大值，所以存在可能，F(n,h-i)计算时i（1<i<h）可以在[1,h]后半部分取值，F(n,h-i)可以在[1,h]后半部分取值。

据此，可以使用二分查找去加速i的取值以省去不必要的计算。优化实现如下：

public class SuperEggDrop { public int superDrop3(int n, int h) { return dp(n, h); } Map<Integer, Integer> memo = new HashMap(); public int dp(int n, int h) { if (!memo.containsKey(h * 100 n)) { int ans; if (h == 0) ans = 0; else if (n == 1) ans = h; else { int lo = 1, hi = h; while (lo 1 < hi) { int x = (lo hi) / 2; int leftVal = dp(n-1, x-1); int rightVal = dp(n, h-x); if (leftVal < rightVal) lo = x; else if (leftVal > rightVal) hi = x; else lo = hi = x; } ans = 1 Math.min(Math.max(dp(n-1, lo-1), dp(n, h-lo)), Math.max(dp(n-1, hi-1), dp(n, h-hi))); } memo.put(h * 100 n, ans); } return memo.get(h * 100 n); } } 二分查找是否为i的最优加速？

上述是通过二分查找来，加速i的取值以省去不必要的计算，这样是不是最优的？

我们，可以用opt(n,h)代表i的最合适取值X0，使得min(max(F(n-1,i-1),F(n,h-i))取到最小值。

此时，我们只需找到合适X0即可，问题由此可以转换为一维数组模型，代码实现如下：

public class SuperEggDrop { public int superDrop4(int K, int N) { // Right now, dp[i] represents dp(1, i) int[] dp = new int[N 1]; for (int i = 0; i <= N; i) dp[i] = i; for (int k = 2; k <= K; k) { // Now, we will develop dp2[i] = dp(k, i) int[] dp2 = new int[N 1]; int x = 1; for (int n = 1; n <= N; n) { // Let's find dp2[n] = dp(k, n) // Increase our optimal x while we can make our answer better. // Notice max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1]) // is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)). while (x < n && Math.max(dp[x-1], dp2[n-x]) > Math.max(dp[x], dp2[n-x-1])) x ; // The final answer happens at this x. dp2[n] = 1 Math.max(dp[x-1], dp2[n-x]); } dp = dp2; } return dp[N]; } }

可以大概比对下，他们的用时

1. https://brilliant.org/wiki/egg-dropping/

2. https://leetcode.com/articles/super-egg-drop/