题目

现在有一座N层高的楼，你的手里有K个鸡蛋，在最坏的情况下，最少需要扔多少次才能确定出刚好会使鸡蛋不会碎掉的楼层F？
注：低于F的楼层，鸡蛋都不会碎掉，大于F的楼层，鸡蛋一定会碎掉。

题目解析

刚读题的我一脸懵逼，什么叫最坏的情况下，最少多少次？
后来经高人指点，大概是这么一个意思：
先说说最坏，我们首先根本不知道鸡蛋到底会在那一层碎掉。
如果一个楼有10层，我们从第一层开始扔，扔到第10层鸡蛋才碎，这就叫运气不好。
我们每一次扔鸡蛋，就可能出现两种情况，碎了或者没碎。而对于碎了，我们就向下面一些的楼层继续，最终能得到一个总的扔的次数。
没碎也是一样，能得到一个总的次数。
我们取次数最多的一个，因为我们运气差。

而对于最少扔的次数，一个楼有许多层，我们可以选择任意一层作为起点开始扔，最终我们能知道从每一层开始，操作的次数是多少。我们选这里面操作次数最少的。
这就是最少扔的次数。

思路

用动态规划的方式解决这道题目。
对于我们的每一次扔鸡蛋，是由这次的结果（碎了，没碎）加上下一次操作的结果数。
假设楼层一共N层，K个鸡蛋，那么在第i层扔的结果应该为：
res=Max(res(K-1,i-1),res(k,N-i))+1
即如果碎了，那么比i高的楼层我们都不找了，相当于我们来到一座新的楼，楼高为i-1层，我们继续在这座楼试一试，并且鸡蛋少了一个。
如果没碎，那么比i低的我们也都不找了，此时我们继续向上找，但最多只会找N-i次，而不是N次了。

那么按照以上的思路，已经可以写出大致的寻找过程。

	public int dp(int K,int N){
		//只剩一个鸡蛋的时候，我们只能一层一层向上找
		if(K==1) return N;
		//第0层的时候，操作数就为0了
		if(N==0) return 0;
		int res = Integer.MAX_VALUE;
		//从第1层开始扔
		for(int i=1;i<N;i++){
			res=Math.min(res,Math.max(
				//碎了
				dp(K-1,i-1),
				//没碎
				dp(K,N-i)
			)+1);//第i层也是一层操作，+1
		}
		return res;
	}

以上的算法就是暴力递归，时间开销非常恐怖。
动态规划其实就是用一个表来记录每一次的查找结果，典型的空间换时间。
这样就能避免重复项的计算

下面修改一下

	 public int superEggDrop(int K, int N) {
		//用一个二维数组，记录每种情况的结果
         	Integer[][] dp = new Integer[K + 1][N + 1];
        	int res = dp(K, N, dp);
	        return res;
   	}
	public int dp(int K,int N,Integer[][] dp){
		//只剩一个鸡蛋的时候，我们只能一层一层向上找
		if(K==1) return N;
		//第0层的时候，操作数就为0了
		if(N==0) return 0;
		//dp表中存在记录，直接读取就行，避免重复计算
		if(dp[K][N]!=null){
			return dp[K][N];
		}
		int res = Integer.MAX_VALUE;
		//从第1层开始扔
		for(int i=1;i<N;i++){
			res=Math.min(res,Math.max(
				//碎了
				dp(K-1,i-1,dp),
				//没碎
				dp(K,N-i,dp)
			)+1);//第i层也是一层操作，+1
		}
		//将计算的结果保存下来
		dp[N][K]=res;
		return res;
	}
	

这样下来，时间复杂度O(KN^2)，空间复杂度O(KN);
其实还有更好的优化，只是我暂时还没彻底消化，理解后会再继续补充.

二分查找优化 2020-4-15

随着扔鸡蛋的进行，我们的dp(K-1,i-1,dp)函数的结果，它是随着i单调递增的。也就是楼层越高，得到的操作数肯定愈多。
而dp(K-1,N-i,dp)一定是单调递减的。因为此时是-i。

我们的最初的策略，假如一个楼有10层，从哪层开始扔最好呢？那我们就每个都试一下，取最终操作数最少的那个结果。所以在前面的代码中，我们用了for循环来遍历i。
但实际上，我们是可以快速逼近这个会令操作数最少的结果的。因为dp(K-1,N-i,dp)单调递减，dp(K-1,i-1,dp)单调递增，两个函数一定会有交点。

而我们，每次取的都是这两个函数的最大值。因为我们要保证运气最差。

而又要我们的操作数最少，那么肯定就是当这两个函数最大值最小的时候，而此时通过上图可以发现，刚好就是两个函数交点。
所以我们只要能快速找到交点，就能迅速确定最合适的i。

因为两个函数都是单调的，所以用二分查找的方式非常好处理。
当dp(K-1,i-1,dp)>dp(K,N-i,dp)的时候，取左半部分。
当dp(K-1,i-1,dp)<dp(K,N-i,dp)的时候，取有半部分。

	//二分查找
    public int dp2(int K, int N, Integer[][] dp) {
        //鸡蛋只剩一个就只能一步一步试
        if (K == 1) return N;
        //楼层为0时候，操作0步
        if (N == 0) return 0;
        if (dp[K][N] != null) {
            return dp[K][N];
        }
        int res = Integer.MAX_VALUE;

        int low = 1, high = N;
        while (low <= high) {
            int mid = (low + high) / 2;
            int broken = dp(K - 1, mid - 1, dp);
            int nBroken = dp(K, N - mid, dp);
            //如果碎了更大,向下二分查找
            if (broken > nBroken) {
                high = mid - 1;
                res = Math.min(res, broken + 1);
            } else {//向上二分查找
                low = mid + 1;
                res = Math.min(res, nBroken + 1);
            }
        }
        dp[K][N] = res;
        return res;
    }

这道题其实还有更加好的优化方法，消化后会继续更新。