小旭讲解 LeetCode 887. Super Egg Drop

BiliBili

YouTube

原题

中文

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

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

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

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

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

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

英文

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 F will break, and any egg dropped at or below floor F will 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

思路

代码

class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, INT_MAX));
        for (int i = 0; i <= N; ++i) {
            dp[0][i] = 0;
            dp[1][i] = i;
        }
        for (int i = 0; i <= K; ++i) {
            dp[i][0] = 0;
        }
        
        for (int k = 2; k <= K; ++k) {
            for (int n = 1; n <= N; ++n) {
                int l = 1, h = n, m = 0;
                while (l <= h) {
                    m = l + (h - l) / 2;
                    int b = dp[k - 1][m - 1], nb = dp[k][n - m];
                    if (b > nb) {
                        h = m - 1;
                    } else {
                        l = m + 1;
                    }
                    dp[k][n] = min(dp[k][n], max(b, nb) + 1);
                }
            }
        }
        return dp[K][N];
    }
};

复杂度分析

• 时间复杂度：O(N*K*\log N)
• 空间复杂度：O(N*K)

参考

原题：https://leetcode.com/problems/super-egg-drop/

本文为原创文章，欢迎分享，勿全文转载，如果内容你实在喜欢，可以加入收藏夹，说不定哪天故事又继续更新了呢。
本文地址：https://qoogle.top/leetcode-887-super-egg-drop/