算法——丢鸡蛋问题

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
leetcode

朴素动态规划

解题思路：
首先是状态表示，利用一个二维数组，两个维度分别表示鸡蛋的数量和楼层数。
然后是状态转转移，从低到高，鸡蛋从少到多，遍历每一种楼层和鸡蛋数量的情况。在求每一种组合情况的时候，再从1遍历楼层，求得对优解。
鸡蛋丢在每一层的情况都是碎或者没有碎。

• 如果碎了，那么临界点就在下面的楼层，同时鸡蛋数减一。
• 如果没碎，那么临界点就在上面的楼层，同时鸡蛋数量不变。
• 然后取上面二者最坏的情况，在加上本次丢的次数1。

先枚举鸡蛋或者先枚举楼层都是可以的。
这里的时间复杂度是N三次方的，在leetcode上会超时。

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] f = new int[K + 1][N + 1];

		// 初始化边界条件
        for(int i = 1; i <= K; i++) f[i][1] = 1;
        for(int i = 1; i <= N; i++) f[1][i] = i; 

        for(int i = 2;  i <= K; i++){
            for(int j = 2; j <= N; j++){
                f[i][j] = f[i - 1][j];
                for(int x = 1; x < j; x++){
                	// 状态转移
                    f[i][j] = Math.min(f[i][j], 1 + Math.max(f[i - 1][x - 1], f[i][j - x]));
                }
            }
        }

        return f[K][N];
    }
}

动态规划+单调决策

在上面的做法中，确定一种蛋楼数组合的时候，求最优值得时候就枚举所有的中间层，这是没有必要的，因为最小值会存在一种单调性，如果检测到小值的时候，不往下枚举了，直接返回。
同时，我们需要保存前一次的最小值的位置，最小值出现的楼层是递增的，我们只需要从上一次的最优值楼层开始比较，就能更快得取得这次楼层得最小值。

这样时间复杂度是N方的。
这里的两次循环中，需要先枚举鸡蛋，然后枚举楼层。二者顺序不能交换。为什么呢？因为我们每次保存着当前蛋数的情况下，上一次最优楼层位置，再下次一增加楼层的时候，只需要从上一次最优楼层位置向下枚举就好，如果改变了楼层和蛋的循环次序，就乱套了。

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] f = new int[K + 1][N + 1];

        for(int i = 0; i <= N; i++) f[1][i] = i;

        for(int i = 1; i <= K; i++) f[i][1] = 1;


        for(int j = 2; j <= K; j++) {
            int cur = 1;
            for(int i = 1; i <= N; i++) {
            	// 当前楼层与下一个楼层进行比较，如果当前楼层的次数更小，说明当前楼层是最优位置
                while(cur < i && Math.max(f[j - 1][cur - 1], f[j][i - cur]) > Math.max(f[j - 1][cur], f[j][i - cur - 1])) cur++;
                f[j][i] = 1 + Math.max(f[j - 1][cur - 1], f[j][i - cur]);
            }
        }

        return f[K][N];
    }
}