Leetcode 887:鸡蛋掉落

题目描述

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

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

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

示例 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 <= K <= 100
1 <= N <= 10000

思路

思路1：基本二维DP + 二分搜索

直接二维DP计算最少的步骤，根据从x层掉落一个鸡蛋得到，则该情况下的状态转移方程为$DP[K][N] = max(DP[K][N-x], DP[K-1][x-1]) + 1$,从而可得到整体的状态转移方程$DP[K][N] = min(max(DP[K][N-x], DP[K-1][x-1])) + 1 x \isin [1, N]$,同时在dp过程中，前一个函数随x单调递减，后面单调递增，所以可以直接求是两个函数最接近的值作为候选求最小（可用两函数比相交（非整数，或者理解为值域相交，在相同定义域内））。所以该过程可用二分法求解。

思路2：二维DP + 逆向思维（根据步骤数和鸡蛋数求楼数）

可理解为有3元的方程，在一定程度上可根据两元求第3个未知变量，根据题设可以得到一个楼层数与鸡蛋数和步骤的关系，即在特定步骤和鸡蛋数下最多可以测的层数。所以可以得到递推式M为步骤数，K为鸡蛋数，所以状态转移方程为$DP[M][K] = DP[M-1][K-1] + DP[M-1][K] + 1$，该方法考虑的是每增加一步，鸡蛋数增加或减少一个，加1相当于在当前层进行操作。状态初始化是可利用任何一个鸡蛋可探明层数为M层，任何1步K个鸡蛋都只能探明1层，在这个过程中K已知，所以可得到一个可定范围

思路3： 逆向思维+推导函数 + 二分搜索

使用思路2进而推导出通项公式$f(k,n) = \frac{n(n-1)…(n-k)}{k!} + \frac{n(n-1)(n-2)}{3!} + \frac{n(n-1)}{2!} + n$,推导过程

代码

思路1代码

public class Solution {
    public int superEggDrop(int K, int N) {
        return eggDropHelper(K, N);
    }

    private static Map eggDPs = new HashMap();

    private String hasHelper(int K, int N) {
        return Integer.toString(K) + "," + Integer.toString(N);
    }

    private int eggDropHelper(int K, int N) {
        if (!eggDPs.containsKey(hasHelper(K, N))) {
            int result = 0;
            if (K == 1 || N == 0 || N == 1) {
                result = N;
            } else {
                int low = 1;
                int high = N;
                while (low + 1 < high) {
                    int mid = (low + high) / 2;
                    int r1 = eggDropHelper(K, N - mid);
                    int r2 = eggDropHelper(K - 1, mid - 1);

                    if (r1 > r2) {
                        low = mid;
                    } else if (r1 < r2) {
                        high = mid;
                    } else {
                        low = high = mid;
                    }
                }
                result = 1 + Math.min(Math.max(eggDropHelper(K, N - low), eggDropHelper(K - 1, low - 1)),
                        Math.max(eggDropHelper(K, N-high), eggDropHelper(K - 1, high - 1)));
            }
            eggDPs.put(hasHelper(K, N), result);
        }
        return eggDPs.get(hasHelper(K, N));
    }
}

思路2代码

public class Solution2 {
    public int superEggDrop(int K, int N) {
        int ans = 0;
        int[] dps = new int[K + 1];
        for (int i = 0; i < K + 1; i ++) {
            dps[i] = 0;
        }
        while (dps[K] < N) {
            for(int i = K; i > 0; i--) {
                dps[i] = 1 + dps[i - 1] + dps[i];
            }
            ans ++;
        }
        return ans;
    }
}

思路3代码

public class Solution3 {
    public int superEggDrop(int K, int N) {
        int low = 1;
        int high = N;
        while (low < high) {
            int mid = (low + high) / 2;
            if (eggHelper(mid, K, N) < N) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private int eggHelper(int mid, int K, int N) {
        int result = 0;
        int r = 1;
        for (int i = 1; i <= K; i++) {
            r *= mid - i + 1;
            r /= i;
            result += r;
            if (result > N) break;
        }
        return result;
    }
}

算法复杂度分析

思路1

时间复杂度

kNlog(N)

空间复杂度

N * N

思路2

时间复杂度

Klog(N)

空间复杂度

N

思路3

时间复杂度

Klog(N)

空间复杂度

1