LeetCode 887. 鸡蛋掉落

发表于 分类于 阅读次数：

  你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
  你知道存在楼层 F，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
  你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

数据范围：1 <= K <= 100 1 <= N <= 10000

示例 1:

1
2
3
4
5
6
7
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2:

1
2
输入：K = 2, N = 6
输出：3

示例 3:

1
2
输入：K = 3, N = 14
输出：4

题解：
  考虑动态规划，我们用 dp[K][N] 表示有 K 个鸡蛋、N 层楼的状态下所需要的最少步数。当我们把一个鸡蛋从第 X 层楼扔下后，会有两种可能的结果：

  • 鸡蛋没碎，那么我们还是有 K 个鸡蛋，但答案只可能在第 X 层以上了，也就是说楼层数变为了 N-X，接下来需要的最少步数为 dp[K][N-X]
  • 鸡蛋碎了，那么我们只剩下 K-1 个鸡蛋了，答案被锁定在下面的 X-1 层楼种，故接下来需要的最少步数为 dp[K-1][X-1]

  因为我们需要考虑的是在最坏情况下所需的步数，所以取二者的最大值作为从第 X 层楼扔下后需要的最少步数。然后，为了让最坏情况下需要的步数最少，我们需要确定究竟哪一个 X 的取值能够使得这个最大值最小。综上，我们可以列出状态转移方程如下：

dp[K][N]=1+min⁡1≤X≤Nmax⁡{dp[K][N−X],dp[K−1][X−1]}dp[K][N]=1+\min_{1\leq X\leq N}{\max\{dp[K][N-X],dp[K-1][X-1]\}}

  有了转移方程，我们就可以求解每个状态的 dp 值了，代码如下：

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
int superEggDrop(int K, int N)
{
    int dp[K+1][N+1];   //存放 superEggDrop(i, j)
    int i, j, p, times;
    for(i = 1; i <= K; ++i)
    {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for(j = 1; j <= N; ++j)
    {
        dp[0][j] = 0;
        dp[1][j] = j;
    }
    for(i = 2; i <= K; ++i)
        for(j = 2; j <= N; ++j)
        {
            // 计算 superEggDrop(i, j)，存入 dp[i][j]
            dp[i][j] = -1;
            for(p = 1; p <= j; ++p)
            {
                // 从第 p 层扔
                times = 1 + max(dp[i-1][p-1], dp[i][j-p]);
                if(dp[i][j] == -1 || times < dp[i][j])
                    dp[i][j] = times;
            }
        }
    return dp[K][N];
}

  考虑一下时间复杂度，一共 O(KN)O(KN) 种状态，每种状态需要枚举 X，耗时为 O(N)O(N)，因此时间复杂度为 O(KN2)O(KN^2)，显然会超时，因此我们需要优化时间复杂度。
  状态数不好优化，那么我们就优化求解每种状态即确定 X 取值的时间复杂度。我们发现，dp[K][N] 是关于 N 的增函数，于是有：

  1. dp[K][N-X] 随 X 增加单调递减
  2. dp[K-1][X-1] 随 X 增加单调递增

  而我们要找的是使得 dp[K][N-X] 和 dp[K-1][X-1] 的最大值最小的 X 的取值，显然，上述两个函数相交即 dp[K][N-X] = dp[K-1][X-1] 时，它们的最大值最小，交点对应的 X 的取值就是我们要找的 X。
  通过以上对单调性的分析，我们就可以通过二分查找找到那个使得 dp[K][N-X] <= dp[K-1][X-1] 的 X 的最小取值。这样，我们就把时间复杂度优化到了 O(KNlog⁡N)O(KN\log 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
29
30
31
32
33
34
35
36
37
int superEggDrop(int K, int N)
{
    int dp[K+1][N+1];   //存放 superEggDrop(i, j)
    int i, j;
    for(i = 1; i <= K; ++i)
    {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for(j = 1; j <= N; ++j)
    {
        dp[0][j] = 0;
        dp[1][j] = j;
    }
    for(i = 2; i <= K; ++i)
        for(j = 2; j <= N; ++j)
        {
            /*
            二分查找使得 dp[i-1][p-1] >= dp[i][j-p] 的 p 的最小取值，
            则 dp[i][j] = min(
                            max(dp[i-1][p-1], dp[i][j-p]),
                            max(dp[i-1][p-2], dp[i][j-p+1])
                          ) + 1
            */
            int l = 1, r = j, mid;
            while(l < r)
            {
                mid = (l+r) / 2;
                if(dp[i-1][mid-1] >= dp[i][j-mid])
                    r = mid;
                else
                    l = mid + 1;
            }
            dp[i][j] = 1 + min(max(dp[i-1][l-1], dp[i][j-l]), max(dp[i-1][l-2], dp[i][j-l+1]));
        }
    return dp[K][N];
}