目录

887_鸡蛋掉落

题目

leetcode # 887. 鸡蛋掉落

你将获得 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)$。当一个函数单调递增而另一个函数单调递减时,我们如何找到一个位置使得它们的最大值最小呢? https://gitee.com/lienhui68/picStore/raw/master/null/20200704022443.png

如上图所示,如果这两个函数都是连续函数,那么我们只需要找出这两个函数的交点,在交点处就能保证这两个函数的最大值最小。但在本题中,$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];
    }

参考

鸡蛋掉落