高楼扔鸡蛋问题（二分解法）

高楼扔鸡蛋问题（二分解法）

二分解法是基于高楼扔鸡蛋的基本动态规划解法。今天就来讲一下高楼扔鸡蛋的第二种解法，二分解法。其实并不是特别难，只不过换了一种遍历的方式。

我们继续看一下这个问题，为什么可以使用二分解法？为什么这道题符合二分搜索的要求？

其实我们只要仔细观察这道题就会发现，我们原来定义的dp[k][n]在有k个鸡蛋，n层楼的最坏情况下扔鸡蛋的最少数目是会随着楼层的减少，扔鸡蛋的次数也会减少。原理很简单。。，你看少了一层楼，那么假设现在有6层楼，我们第一种方案就是一层一层的扔，最坏情况就是扔6次，如果减少了一层就是5层，只需要扔5次就好了。换一个角度看待高楼扔鸡蛋问题，就是不同策略下最坏情况的扔鸡蛋数，对比哪个策略扔的最少。无论鸡蛋在哪个楼层扔下去碎掉，我们都可以发现，无论用哪一种策略，我们都可以找到它扔鸡蛋数目最多的那一次，怎么找，我们一开始就是所有楼层都去遍历来慢慢找，然后交给递归来给我们解决找到答案就好了。

那么我们这样全部都遍历是不是就很蠢。特别慢。我们上面说了，楼层减少，其实扔鸡蛋数也在减少，也就是说dp数组的值也在减少。楼层增多，扔鸡蛋数也会增多。那么也就是说我们的高楼扔鸡蛋的函数其实就是一个单调函数？我们有两种情况，一种就是鸡蛋碎了，下一层楼，一种是鸡蛋没碎，上一层楼对吧。也就是说有两个函数，而且这两个函数都是单调的，而且有可能会有交点，即使没有也无所谓，毕竟我们只是要找最少的扔鸡蛋个数。

图画的有点丑哈哈。
其实就是minEgg(k-1,mid-1),和minEgg(k,n-mid)两个以mid为变量的两个函数，都是单调函数。绿色的线就是每一次二分取到的位置，它们肯定有一个大有一个小的，我们的目标就是每一次都要取大的那个，因为是最坏情况，扔鸡蛋数目最多的。你们会发现取的都是上面的，没错其实就是交点上面能够取到所有的值里面找到最小的那个就对了，也就是最坏情况下扔鸡蛋数目最少的了。红色的点就是交点，蓝色的点就是我们有可能会取到的点。其实思路和基本的动态规划没什么不同，只是做了一个二分的优化而已。只需要掌握基本的解法，然后再来套用二分就不难了

代码：

  public static int superEggDrop2(int K,int N,int[][] dp){
//        如果鸡蛋只剩下一个了，那肯定只能一层一层来了，那肯定就是要扔N层（按照最坏情况）if(K==1) return N;
//        如果楼层都遍历完毕了if(N==0) return 0;
//        备忘录if(dp[K][N]!=0) return dp[K][N];int left=1;int right=N;int res=Integer.MAX_VALUE;//        二分搜索while(left<=right){int mid=(left+right)/2;int broken=superEggDrop2(K-1,mid-1,dp);int unbroken=superEggDrop2(K,N-mid,dp);if(broken>=unbroken){right=mid-1;res=Math.min(res,broken+1);}else{left=mid+1;res=Math.min(res,unbroken+1);}}dp[K][N]=res;return res;}