887_鸡蛋掉落

2020-07-12 约 1985 字预计阅读 4 分钟次阅读

题目

你将获得 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 是多少。

分析

假设鸡蛋从X楼层落下碎了，那么接下来得从0到X-1楼层测试且鸡蛋个数-1，否则从X+1楼层测试剩余的(n-x)层，鸡蛋个数不变。 $f(k, n)$表示剩余k个鸡蛋，还有n层楼等待测试确定f的最小次数, x表示从第几层楼开始测试 $f(k,n) = min(max{f(k-1,x-1), f(k, n-x)} + 1$, 其中f[k][n]) i=1 则f=N，i=0 则f=0; k = 0则f= 0; 相当于把一楼层从x层一分为2，分别在两座楼上测试，然后取两者较大的次数。x从1到n

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


    public static int superEggDrop(int K, int N) {
        // 状态定义i：剩余鸡蛋个数 j：楼层高度
        int[][] f = new int[K + 1][N + 1];
        // 初始化
        for (int n = 0; n <= N; n++) {
            // 当鸡蛋个数只有1个时，f = 楼层高度
            f[0][n] = 0;
            f[1][n] = n;
        }
        for (int k = 0; k <= K; k++) {
            f[k][0] = 0;
        }

        for (int k = 2; k <= K; k++) {
            for (int n = 1; n <= N; n++) {
                // x 2->100
                int temp = Integer.MAX_VALUE;
                for (int x = 1; x <= n; x++) {
                    // 楼层一分为2， 分别进行测试
                    // 取2部分结果的最大值 再跟上次测出来的f进行比较， 取较小的值就是最优解
                    temp = Math.min(temp, Math.max(f[k - 1][x - 1], f[k][n - x]) + 1);
                }
                f[k][n] = temp;
            }
        }

        return f[K][N];
    }

时间复杂度优化

如果我们直接暴力转移求解每个状态的dp值，时间复杂度是为 $O(KN^2)$，即一共有 $O(KN)$个状态，对于每个状态枚举扔鸡蛋的楼层 X，需要O(N)的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。我们观察到dp(K,N)是一个关于 NN 的单调递增函数，也就是说在鸡蛋数 KK 固定的情况下，楼层数 N越多，需要的步数一定不会变少。在上述的状态转移方程中，第一项 $T_1(X)=dp(K−1,X−1)$是一个随 XX 的增加而单调递增的函数，第二项$T_2(X)=dp(K,N-X)$是一个随着 XX 的增加而单调递减的函数。

这如何帮助我们来优化这个问题呢？当X增加时，$T_1(X)$单调递增而$T_2(X)$单调递减，我们可以想象在一个直角坐标系中，横坐标为X，纵坐标为$T_1(X)$和$T_2(X)$。当一个函数单调递增而另一个函数单调递减时，我们如何找到一个位置使得它们的最大值最小呢？

如上图所示，如果这两个函数都是连续函数，那么我们只需要找出这两个函数的交点，在交点处就能保证这两个函数的最大值最小。但在本题中，$T_1(X)$和$T_2(X)$都是离散函数，也就是说，X的值只能取1，2，3等等。在这种情况下，我们需要找到最大的满足$T_1(X) < T_2(X)$的$X_0$，以及最小的满足$T_1(X) \ge T_2(X)$的$X_1$,对应到上图中，就是离这两个函数（想象中的）交点左右两侧最近的整数。

我们只需要比较在$X_0$和$X_1$处两个函数的最大值，取一个最小的作为X即可。在数学上，我们可以证明$X_0$和$X_1$相差1，这也是比较显然的，因为它们正好夹住了那个想象中的交点，并且相距尽可能地近。因此我们就可以使用二分查找的方法找$X_0$，再得到$X_1$。

二分查找的写法因人而异，本质上我们就是需要找到最大的满足$T_1(X) < T_2(X)$的$X_0$，根据$X_mid$进行二分边界的调整。在得到了$X_0$之后，我们可以知道$X_1=X_0 + 1$。此时我们只需要比较$max(T_1(X_0), T_2(X_0))$ 和 $max(T_1(X_1), T_2(X_1))$，取较小的那个值作为dp值即可。

这样一来，对于给定的状态$(K, N)$，我们只需要$O(logN)$的时间，通过二分查找就能得到最优的那个X，因此时间复杂度从$O(KN^2)$降低至$O(KNlogN)$，可以通过本题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


    public static int superEggDrop(int K, int N) {
        // 状态定义i：剩余鸡蛋个数 j：楼层高度
        int[][] f = new int[K + 1][N + 1];
        // 初始化
        for (int n = 0; n <= N; n++) {
            // 当鸡蛋个数只有1个时，f = 楼层高度
            f[0][n] = 0;
            f[1][n] = n;
        }
        for (int k = 0; k <= K; k++) {
            f[k][0] = 0;
        }

        for (int k = 2; k <= K; k++) {
            for (int n = 1; n <= N; n++) {
                int lo = 1, hi = n, x;
                while (lo + 1 < hi) {
                    x = (lo + hi) / 2;
                    int t1 = f[k - 1][x - 1];
                    int t2 = f[k][n - x];
                    if (t1 < t2) {
                        lo = x;
                    } else if (t1 > t2) {
                        hi = x;
                    } else {
                        lo = hi = x;
                    }
                }
                f[k][n] = Math.min(Math.max(f[k - 1][lo - 1], f[k][n - lo]), Math.max(f[k - 1][hi - 1], f[k][n - hi])) + 1;
            }
        }

        return f[K][N];
    }

参考

鸡蛋掉落

目录

887_鸡蛋掉落

题目

分析

代码

时间复杂度优化

参考