鸡蛋掉落

简介

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 f 确切的值的最小操作次数是多少？

输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

思路一：动态规划

dp[i][j] 表示有 i 颗鸡蛋，j 层楼时需要实验的最少次数
遍历 dp，dp[i][j] 的确定需要确定要先选 1~i 的哪一层，所以必须从 1~n 遍历，分别查看在这一层中会碎和不会碎的情况，在挑选出最少次数的那一层

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        // 初始化 dp
        for (int i = 1; i <= N; i++) {
            dp[1][i] = i;
        }
        for (int i = 2; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                int min = dp[i-1][j];
                // 从 1 ~ j 层中挑选出一层来投，使得次数最少
                for (int k = 1; k < j; k++) {
                    min = Math.min(min, 1 + Math.max(dp[i-1][k-1], dp[i][j-k]));
                }
                dp[i][j] = min;
            }
        }
        return dp[K][N];
    }
}

思路二：二分法优化

从上面的 max(dp[i-1][k-1], dp[i][j-k]) 入手，我们知道，当 i 不变时，j 越大，则 dp[i][j] 越大
所以，dp[i-1][k-1] 会随着 k 的增大而单调递增
dp[i][j-k] 会随着 k 的增大而单调递减

如图所示，我们只需要找到这两个函数的交点，就能保证在这个点下，这两个函数的最大值最小，所以我们可以用二分法来定位这个点。

当在此点下，如果 dp[i-1][k-1] 的值小于 dp[i][j-k]，则范围向右缩小
当在此点下，如果 dp[i-1][k-1] 的值大于 dp[i][j-k]，则范围向左缩小
否则此点就是最小值的点

 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


class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        // 初始化 dp
        for (int i = 1; i <= N; i++) {
            dp[1][i] = i;
        }
        for (int i = 2; i <= K; i++) {
            Work:
            for (int j = 1; j <= N; j++) {
                int l = 1, r = j;
                // 二分法，找到上图中最小的点
                while (l <= r) {
                    int m = (l + r) >> 1;
                    int lowVal = dp[i-1][m-1], highVal = dp[i][j - m];
                    if (lowVal < highVal) {
                        l = m+1;
                    } else if (lowVal > highVal) {
                        r = m-1;
                    } else {
                        // 如果相等，则直接给出答案
                        dp[i][j] = 1 + dp[i-1][m-1];
                        continue Work;
                    }
                }
                // 如果相交的点不是自然数，则需要判断相交点的左右两个自然数
                dp[i][j] = 1 + Math.min(Math.max(dp[i-1][l-1], dp[i][j - l]), 
                        Math.max(dp[i-1][r-1], dp[i][j - r]));
            }
        }
        return dp[K][N];
    }
}

来源： LC 887.鸡蛋掉落

简介

思路一：动态规划

思路二：二分法优化

相关文章：