LEETCODE 887. Super Egg Drop 鸡蛋掉落问题分析

题目大意：

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：

输入：K = 2, N = 6
输出：3

示例 3：

输入：K = 3, N = 14
输出：4

提示：

1. 1 <= K <= 100
2. 1 <= N <= 10000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=887

解题思路：

说实话，第一次读完题目之后有些懵，题目确实比较绕。简单来说，题目大概是这个意思，你有一些完全相同的鸡蛋，目的是测试从最高多少层楼扔下来鸡蛋不会碎掉。但测试时要遵守以下条件：

1. 鸡蛋碎了就不能再次使用，反之还可以再次利用。
2. 必须在鸡蛋用完之前测出结果。
3. 不论鸡蛋碎与否，每扔一次鸡蛋算走了一步，要求求出能得出结论的最少步数。

这是典型的利用动态规划(DP)解题的题目。动态规划题目的典型特点就是：一个问题可以拆分成子问题，并且子问题与原问题是同一个思考逻辑。比如用本题来举例，随便找一楼层扔鸡蛋，如果碎了，说明目标楼层在当前楼层之下，然后在低于当前的楼层之中再随便找一层楼去扔，这时的思考逻辑等同于第一次。如果没碎，则说明目标楼层在当前之上，同样再找一层去扔，这时的思考逻辑也与第一次扔时相同。以此类推，直到找到目标楼层为止。这就是动态规划的思想。利用此算法来解题，关键一点是要推导出计算公式，下面我们来看看如何把这个公式写出来。

我们先从简单的方面去思考。如果你只有一个鸡蛋，那么你就千万不能随便乱扔，因为一旦鸡蛋摔碎，你就Game Over了！所以你只能从一楼向上逐层测试，直到哪一层鸡蛋碎掉了，则说明目标楼层为当前楼层的下一层，这时使用的步数为当前楼层数。不过，我们应该考虑问题的最坏情况，即一直需要测试到顶楼鸡蛋才碎(或者还没碎)。不论在顶楼鸡蛋碎与否，我们都能得到目标楼层（碎了，目标楼层 = 顶楼 – 1，没碎，目标楼层 = 顶楼）。因此，当鸡蛋只有一个时，考虑最坏情况下测出目标楼层的最优解为楼层数。

在这插一句话，有人问我，在这里为什么要考虑最坏情况？不是求最少步数吗？

大家注意一下，最少步数是要满足一定能测出目标楼层的最少步数。我们都不是脸帝，不可能每次随便找一楼层扔一次就恰好是目标楼层。

再来想另一种比较简单的条件，如果楼层只有一层呢？那么只要你手里有没碎的鸡蛋，扔一次就能判断出目标楼层。（碎了，目标楼层为0，没碎为1）

当然还有一种情况便是，楼层为0，或者鸡蛋数为0，那我们还测个毛线，结果肯定是0。

好，总结一下上面说的几种简单的情况，即：

int result;
// 楼层数为0 或者 鸡蛋数为0
if(N == 0 || K == 0) {
    result = 0;
}
// 楼层数为1
if(N == 1) {
    result = 1;
}
// 鸡蛋数为1
if(K == 1) {
    result = N;
}

接下来是重点，我们看看在鸡蛋数与楼层数都大于1的时候我们需要如何思考？

先假设我们在随便一层扔下鸡蛋，如果鸡蛋碎了，说明目标楼层在当前之下。反之，鸡蛋没碎，那么我们还需要继续向楼上进行测试。也就是说，在当前楼层测试过后，我们以当前楼层为基准将大楼分成了上下两个部分，因为鸡蛋要么碎掉，要么不碎，两种状态不可能同时发生，所以，接下来我们要么在上部继续测试，要不在下部继续测试，两边最坏的情况(也就是使用步数最多)便是当前层测出结果所需要的步数。

为了方便理解，我们举例来说明，比如有一个10层高的楼，我们手中有5个鸡蛋，如果我们在第三层测试后，鸡蛋碎了，则我们需要利用剩下的4个鸡蛋继续在前2层中测试，反之鸡蛋没碎，我们则需要利用剩下的5个鸡蛋在4-10层中继续测试，因此，得出结论，设dp[k][n]表示拥有k个鸡蛋测试高度为n楼所需的步数，那么,当当前楼层为x时：

dp[k][n] = Math.max(dp[k-1][x-1], db[k][n-x]) + 1;
// dp[k-1][x-1]为: k-1表示鸡蛋碎了; x-1表示当前之下的楼层
// db[k][n-x]为: k表示鸡蛋没碎; n-x表示当前之上的楼层
// 求max为了满足最坏情况
// 最后加一目的是算上当前在楼层x的这一步测试

以上，我们只考虑了在x楼测试的情况，实际上x是需要从1 到N进行遍历测试，并从中找到最优解（前文说过，我们不是脸帝，不可能随便选一层就是目标楼层）。因此，最终的表达式应为：

min{Math.max(dp[k-1][x-1], db[k][n-x]) + 1}; // x=[1,2,3,4,...N]

我们依照以上思路，试着写一下代码：

public int superEggDrop(int K, int N) {
    int dp[][] = new int[K + 1][N + 1];
    for (int k = 0; k <= K; k++) {
        dp[k][0] = 0;
        dp[k][1] = 1;
    }
    for (int n = 0; n <= N; n++) {
        dp[0][n] = 0;
        dp[1][n] = n;
    }
    for (int n = 2; n <= N; n++) {
        for (int k = 2; k <= K; k++) {
            dp[k][n] = Integer.MAX_VALUE;
            for (int x = 1; x <= n; x++) {
                dp[k][n] = Math.min(dp[k][n], Math.max(dp[k - 1][x - 1], dp[k][n - x]) + 1);
            }
        }
    }
    return dp[K][N];
}

这种解法套了三层循环，顺序计算出了：

1. 当共2层楼2个鸡蛋时，从1层到2层分别测试所需要的步数中的最小值
2. 当共2层楼3个鸡蛋时，从1层到2层分别测试所需要的步数中的最小值
3. …
4. 当共2层楼K个鸡蛋时，从1层到2层分别测试所需要的步数中的最小值
5. 当共3层楼2个鸡蛋时，从1层到3层分别测试所需要的步数中的最小值
6. …
7. 当共N层楼K个鸡蛋时，从1层到K层分别测试所需要的步数中的最小值

时间复杂度为O(N*K*N)，在LeetCode提交之后，LTE时间超时了。不过，动态规划的思想我们应该已经掌握，接下来我们看看哪里可以优化一下。

我们看下代码的关键部分：

for (int x = 1; x <= n; x++) {
    dp[k][n] = Math.min(dp[k][n], Math.max(dp[k - 1][x - 1], dp[k][n - x]) + 1);
}

这是三层循环中的最内层，目的是要找出当已知拥有k个鸡蛋和n层楼时，在哪一层开始测试可以得到最优解。所谓最优解，其实是找出所有Math.max(dp[k – 1][x – 1], dp[k][n – x])中最小的那个。我们仔细看下max中的两个元素：
dp[k – 1][x – 1]
dp[k][n – x]
本层循环是x在递增，很显然，在k和n不变的情况下，dp[k – 1][x – 1]会随着x的增大而增大（鸡蛋数不变，楼层数增多）， dp[k][n – x]会随着x的增加而减少（鸡蛋数不变，楼层数减少）。更形象的描述一下，比如我们在大楼中随便用一层将他分成两部分，如果用于分割的这层越靠近下面，则下面这部分楼层数越少，上面的楼层数越多，所以下面测试的步数就会越少，上面测试的步数会越多。反之，如果分割层越靠近顶楼，则上面楼层越少，下面楼层越多。因此，上部楼层测试数越接近（或者相等）下部楼层测试数，那么这个max值一定是当前最优解。

这样，问题就转化为如何找到这个临界值。这个临界值可能是一个楼层，即当前楼层之上的测试步数R1等于当前之下的测试步数R2。临界值也可能是两个楼层，其中的一层R1>R2，其相邻一层R1<R2。我们可以用二分法来找，这样代码的效率就提高到了O(N*K*LogN)，看下代码：

public int superEggDrop(int K, int N) {
    int dp[][] = new int[K + 1][N + 1];
    for (int k = 0; k <= K; k++) {
        dp[k][0] = 0;
        dp[k][1] = 1;
    }
    for (int n = 0; n <= N; n++) {
        dp[0][n] = 0;
        dp[1][n] = n;
    }
    for (int n = 2; n <= N; n++) {
        for (int k = 2; k <= K; k++) {
            dp[k][n] = Integer.MAX_VALUE;
            int start = 1;
            int end = n;
            while (start < end) {
                int mid = (end + start) / 2;
                if (dp[k - 1][mid - 1] < dp[k][n - mid]) {
                    start = mid + 1;
                } else if (dp[k - 1][mid - 1] > dp[k][n - mid]) {
                    end = mid - 1;
                } else {
                    start = mid;
                    end = mid;
                }
            }

            dp[k][n] = Math.min(Math.max(dp[k - 1][start - 1], dp[k][n - start]) + 1,
                    Math.max(dp[k - 1][end], dp[k][n - end]) + 1);
        }
    }
    return dp[K][N];
}

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-887-super-egg-drop-鸡蛋掉落问题分析/