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. 当共2层楼K个鸡蛋时,从1层到2层分别测试所需要的步数中的最小值
  4. 当共3层楼2个鸡蛋时,从1层到3层分别测试所需要的步数中的最小值
  5. 当共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-鸡蛋掉落问题分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。