887. Super Egg Drop

You are given K eggs, and you have access to a building with N floors from 1 to N

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than Fwill break, and any egg dropped at or below floor Fwill not break.

Each  move , you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

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

这道题说给了我们K个鸡蛋,还有一栋共N层的大楼,说是鸡蛋有个临界点的层数F,高于这个层数扔鸡蛋就会碎,否则就不会,问我们找到这个临界点最小需要多少操作,注意这里的操作只有当前还有没碎的鸡蛋才能进行。这道题是基于经典的扔鸡蛋的问题改编的,原题是有 100 层楼,为了测鸡蛋会碎的临街点,最少可以扔几次?答案是只用扔 14 次就可以测出来了,讲解可以参见油管上的这个视频,这两道题看着很相似,其实是有不同的。这道题限制了鸡蛋的个数K,假设我们只有1个鸡蛋,碎了就不能再用了,这时我们要测 100 楼的临界点的时候,只能一层一层去测,当某层鸡蛋碎了之后,就知道临界点了,所以最坏情况要测 100 次,注意要跟经典题目中扔 14 次要区分出来。那么假如有两个鸡蛋呢,其实需要的次数跟经典题目中的一样,都是 14 次,这是为啥呢?因为在经典题目中,我们是分别间隔 14,13,12,…,2,1,来扔鸡蛋的,当我们有两个鸡蛋的时候,我们也可以这么扔,第一个鸡蛋仍在 14 楼,若碎了,说明临界点一定在 14 楼以内,可以用第二个鸡蛋去一层一层的测试,所以最多操作 14 次。若第一个鸡蛋没碎,则下一次扔在第 27 楼,假如碎了,说明临界点在 (14,27] 范围内,用第二个鸡蛋去一层一层测,总次数最多 13 次。若第一个鸡蛋还没碎,则继续按照 39, 50, …, 95, 99,等层数去测,总次数也只可能越来越少,不会超过 14 次的。但是照这种思路分析的话,博主就不太清楚有3个鸡蛋,在 100 楼测,最少的步骤数,答案是9次,博主不太会分析怎么测的,各位看官大神知道的话一定要告诉博主啊。

其实这道题比较好的解法是用动态规划 Dynamic Programming,因为这里有两个变量,鸡蛋数K和楼层数N,所以就要使用一个二维数组 DP,其中 dp[i][j] 表示有i个鸡蛋,j层楼要测需要的最小操作数。那么我们在任意k层扔鸡蛋的时候就有两种情况(注意这里的k跟鸡蛋总数K没有任何关系,k的范围是 [1, j]):

  • 鸡蛋碎掉:接下来就要用 i-1 个鸡蛋来测 k-1 层,所以需要 dp[i-1][k-1] 次操作。
  • 鸡蛋没碎:接下来还可以用i个鸡蛋来测 j-k 层,所以需要 dp[i][j-k] 次操作。
    因为我们每次都要面对最坏的情况,所以在第j层扔,需要 max(dp[i-1][k-1], dp[i][j-k])+1 步,状态转移方程为:

dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1) ( 1 <= k <= j )

这种写法会超时 Time Limit Exceeded,代码请参见评论区1楼,OJ 对时间卡的还是蛮严格的,所以我们就需要想办法去优化时间复杂度。这种写法里面我们枚举了 [1, j] 范围所有的k值,总时间复杂度为 O(KN^2),若我们仔细观察 dp[i - 1][k - 1] 和 dp[i][j - k],可以发现前者是随着k递增,后者是随着k递减,且每次变化的值最多为1,所以只要存在某个k值使得二者相等,那么就能得到最优解,否则取最相近的两个k值做比较,由于这种单调性,我们可以在 [1, j] 范围内对k进行二分查找,找到第一个使得 dp[i - 1][k - 1] 不小于 dp[i][j - k] 的k值,然后用这个k值去更新 dp[i][j] 即可,这样时间复杂度就减少到了 O(KNlgN),其实也是险过,参见代码如下:

解法一:

class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1));
        for (int j = 1; j <= N; ++j) dp[1][j] = j;
        for (int i = 2; i <= K; ++i) {
            for (int j = 1; j <= N; ++j) {
                dp[i][j] = j;
                int left = 1, right = j;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (dp[i - 1][mid - 1] < dp[i][j - mid]) left = mid + 1;
                    else right = mid;
                }
                dp[i][j] = min(dp[i][j], max(dp[i - 1][right - 1], dp[i][j - right]) + 1);
            }
        }
        return dp[K][N];
    }
};

进一步来想,对于固定的k,dp[i][j-k] 会随着j的增加而增加,最优决策点也会随着j单调递增,所以在每次移动j后,从上一次的最优决策点的位置来继续向后查找最优点即可,这样时间复杂度就优化到了 O(KN),我们使用一个变量s表示当前的j值下的的最优决策点,然后当j值改变了,我们用一个 while 循环,来找到第下一个最优决策点s,使得 dp[i - 1][s - 1] 不小于 dp[i][j - s],参见代码如下:
解法二:

class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1));
        for (int j = 1; j <= N; ++j) dp[1][j] = j;
        for (int i = 2; i <= K; ++i) {
            int s = 1;
            for (int j = 1; j <= N; ++j) {
                dp[i][j] = j;
                while (s < j && dp[i - 1][s - 1] < dp[i][j - s]) ++s;
                dp[i][j] = min(dp[i][j], max(dp[i - 1][s - 1], dp[i][j - s]) + 1);
            }
        }
        return dp[K][N];
    }
};

其实我们还可以进一步优化时间复杂度到 O(KlgN),不过就比较难想到了,需要将问题转化一下,变成已知鸡蛋个数,和操作次数,求最多能测多少层楼的临界点。还是使用动态规划 Dynamic Programming 来做,用一个二维 DP 数组,其中 dp[i][j] 表示当有i次操作,且有j个鸡蛋时能测出的最高的楼层数。再来考虑状态转移方程如何写,由于 dp[i][j] 表示的是在第i次移动且使用第j个鸡蛋测试第 dp[i-1][j-1]+1 层,因为上一个状态是第i-1次移动,且用第j-1个鸡蛋。此时还是有两种情况:

  • 鸡蛋碎掉:说明至少可以测到的不会碎的层数就是 dp[i-1][j-1]。
  • 鸡蛋没碎:那这个鸡蛋可以继续利用,此时我们还可以再向上查找 dp[i-1][j] 层。

那么加上当前层,总共可以通过i次操作和j个鸡蛋查找的层数范围是 [0, dp[i-1][j-1] + dp[i-1][j] + 1],这样就可以得到状态转移方程如下:

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1

当 dp[i][K] 正好小于N的时候,i就是我们要求的最小次数了,参见代码如下:

解法三:

class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(N + 1, vector<int>(K + 1));
        int m = 0;
        while (dp[m][K] < N) {
            ++m;
            for (int j = 1; j <= K; ++j) {
                dp[m][j] = dp[m - 1][j - 1] + dp[m - 1][j] + 1;
            }
        }
        return m;
    }
};

我们可以进一步的优化空间,因为当前的操作次数值的更新只跟上一次操作次数有关,所以我们并不需要保存所有的次数,可以使用一个一维数组,其中 dp[i] 表示当前次数下使用i个鸡蛋可以测出的最高楼层。状态转移方程的推导思路还是跟上面一样,参见代码如下:
解法四:

class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<int> dp(K + 1);
        int res = 0;
        for (; dp[K] < N; ++res) {
            for (int i = K; i > 0; --i) {
                dp[i] = dp[i] + dp[i - 1] + 1;
            }
        }
        return res;
    }
};

下面这种方法就非常的 tricky 了,居然推导出了使用k个鸡蛋,移动x次所能测的最大楼层数的通项公式,推导过程可以参见这个帖子,通项公式如下: f(k,x) = x(x-1)..(x-k)/k! + ... + x(x-1)(x-2)/3! + x(x-1)/2! + x 这数学功底也太好了吧,有了通向公式后,我们就可以通过二分搜索法 Binary Search 来快速查找满足题目的x。这里其实是博主之前总结贴 LeetCode Binary Search Summary 二分搜索法小结 中的第四类,用子函数当作判断关系,这里子函数就是用来实现上面的通向公式的,不过要判断,当累加和大于等于N的时候,就要把当的累加和返回,这样相当于进行了剪枝,因为在二分法中只需要知道其跟N的大小关系,并不 care 到底大了多少,这样快速定位x的方法运行速度貌似比上面的 DP 解法要快不少,但是这通项公式尼玛谁能容易的推导出来,只能膜拜叹服了,参见代码如下:
解法五:

class Solution {
public:
    int superEggDrop(int K, int N) {
        int left = 1, right = N;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (helper(mid, K, N) < N) left = mid + 1;
            else right = mid;
        }
        return right;
    }
    int helper(int x, int K, int N) {
        int res = 0, r = 1;
        for (int i = 1; i <= K; ++i) {
            r *= x - i + 1;
            r /= i;
            res += r;
            if (res >= N) break;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/887

参考资料:

https://leetcode.com/problems/super-egg-drop/

https://www.cnblogs.com/Phantom01/p/9490508.html

https://www.acwing.com/solution/leetcode/content/579/

https://leetcode.com/problems/super-egg-drop/discuss/159508/easy-to-understand

https://leetcode.com/problems/super-egg-drop/discuss/299526/BinarySearch-or-Easiest-or-Explanation

https://leetcode.com/problems/super-egg-drop/discuss/158974/C%2B%2BJavaPython-2D-and-1D-DP-O(KlogN)

https://leetcode.com/problems/super-egg-drop/discuss/181702/Clear-C%2B%2B-codeRuntime-0-msO(1)-spacewith-explation.No-DPWhat-we-need-is-mathematical-thought!

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation