leetcode-887-Super Egg Drop

leetcode 887

问题

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

分析

思路1: $dp[k][n]$ 表示手头上有 k 个鸡蛋，现在要测试的楼层有 N 层，包含 0 层。于是我们可以选择从 第 $i$ 层开始往下扔鸡蛋，$i \in [1, N]$。鸡蛋有两种情况，鸡蛋碎掉了，和鸡蛋没有碎掉。于是可以有如下的状态转移方程：
$$
dp[k][n] = min(dp[k][n], 1+max(dp[k-1][i-1], dp[k][n-i])); \; i \in [1,n]
$$
时间复杂度为 $O(KN^2)$，TLE

思路2: 二分搜索优化 根据思路1中定义的DP，在每一次遍历 $i$ 时，dp 的第一维是没有变化的，因此随着第二维楼层的增加，$dp[k][n]$ 呈现一种单调递增的现象。因此，随着 $i$ 的增加 $dp[k-1][i-1]$ 单调递增，$dp[k][n-i]$ 单调递减。于是，$max(dp[k-1][i-1], dp[k][n-i])$ 是一个折线，并有一个低谷，这个低谷位置的 $i$ 就是我们的最佳测试楼层。

在低谷的左侧 $dp[K, N-i] > dp[K-1][i-1]$ 右侧 $dp[K, N-i] < dp[K-1][i-1]$。寻找最小的 $i$ 使其满足 $dp[K, N-i] \leq dp[K-1][i-1]$。

思路3: 重新定义状态转移 定义 $dp[k][m] = n$ 表示当有 k 个鸡蛋，可以尝试扔 m 次鸡蛋，最坏情况下最多能确切测试一栋 n 层的楼。于是状态转移方程：
$$
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
$$

表示我们尝试在一个楼层扔鸡蛋，如果鸡蛋碎了，那么我们可以确定Floor在测试楼层的下面部分，也就是说其上部分是没有的，如果没有碎，则说明Floor 在则是楼层的上面部分，下面部分是没有的。

if egg breaks, then we can check dp[m - 1][k - 1] floors.
if egg doesn’t breaks, then we can check dp[m - 1][k] floors.

其中 +1 是因为当前楼层，通过排除法可以增加1层楼的确定。通过状态压缩可以将空间复杂度降低一维。后面根据单调性可以优化到 $O(KlogN)$

代码1

//TLE O(KN^2)
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[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) {
                for (int i = 1; i <= n; ++i) {
                    dp[k][n] = min(dp[k][n], 1+max(dp[k-1][i-1], dp[k][n-i]));
                }
            }
        }
        return dp[K][N];
    }
};

代码2

// O(KNlogN)
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[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 lo = 1, hi = n;
                while (lo <= hi) {
                    int mi = lo + (hi-lo)/2;
                    int b  = dp[k-1][mi-1];
                    int nb = dp[k][n-mi];
                    if (nb < b) {
                        hi = mi - 1;
                    } else {
                        lo = mi + 1;
                    }
                    dp[k][n] = min(dp[k][n], 1+max(b, nb));
                }
                /**
                for (int i = 1; i <= n; ++i) {
                    dp[k][n] = min(dp[k][n], 1+max(dp[k-1][i-1], dp[k][n-i]));
                }
                **/
            }
        }
        return dp[K][N];
    }
};

代码3

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