题目链接

LeetCode

题目描述

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

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

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

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

示例 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 <= 104

    解题思路

    方法一:动态规划+二分查找

    我们可以考虑使用动态规划来做这道题,状态可以表示成 (k,n),其中 k 为鸡蛋数,n 为楼层数。当我们从第 x 楼扔鸡蛋的时候:

  • 如果鸡蛋不碎,那么状态变成 (k,n−x),即我们鸡蛋的数目不变,但答案只可能在上方的 n−x 层楼了。也就是说,我们把原问题缩小成了一个规模为 (k,n−x) 的子问题;

  • 如果鸡蛋碎了,那么状态变成 (k−1,x−1),即我们少了一个鸡蛋,但我们知道答案只可能在第 x 楼下方的 x−1 层楼中了。也就是说,我们把原问题缩小成了一个规模为 (k−1,x−1) 的子问题。

这样一来,我们定义 dp(k,n) 为在状态 (k,n)下最少需要的步数。根据以上分析我们可以列出状态转移方程:

这个状态转移方程是如何得来的呢?对于 dp(k,n) 而言,我们像上面分析的那样,枚举第一个鸡蛋扔在的楼层数 x。由于我们并不知道真正的 f 值,因此我们必须保证 鸡蛋碎了之后接下来需要的步数鸡蛋没碎之后接下来需要的步数 二者的 最大值 最小,这样就保证了在 最坏情况下(也就是无论 f 的值如何) dp(k,n) 的值最小。如果能理解这一点,也就能理解上面的状态转移方程,即最小化 max(dp(k−1,x−1),dp(k,n−x))

如果我们直接暴力转移求解每个状态的 dp 值,时间复杂度是为 O(kn^2),即一共有 O(kn) 个状态,对于每个状态枚举扔鸡蛋的楼层 x,需要 O(n) 的时间。这无疑在当前数据范围下是会超出时间限制的,因此我们需要想办法优化枚举的时间复杂度。

我们观察到 dp(k,n) 是一个关于 n 的单调递增函数,也就是说在鸡蛋数 k 固定的情况下,楼层数 n 越多,需要的步数一定不会变少。在上述的状态转移方程中,第一项 T1(x)=dp(k−1,x−1) 是一个随 x 的增加而单调递增的函数,第二项 T2(x)=dp(k,n−x) 是一个随着 x 的增加而单调递减的函数。

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

887. 鸡蛋掉落*** - 图1

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

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

  • 我们在所有满足条件的 x 上进行二分查找。对于状态 (k,n) 而言,x 即为 [1,n] 中的任一整数;
  • 在二分查找的过程中,假设当前这一步我们查找到了 887. 鸡蛋掉落*** - 图2,如果 887. 鸡蛋掉落*** - 图3,那么真正的 x0 一定在 887. 鸡蛋掉落*** - 图4 的左侧,否则真正的 x0 在 887. 鸡蛋掉落*** - 图5 的右侧。

二分查找的写法因人而异,本质上我们就是需要找到最大的满足 887. 鸡蛋掉落*** - 图6 的 x0,根据 887. 鸡蛋掉落*** - 图7 进行二分边界的调整。在得到了 x0 后,我们可以知道 x1 即为 x0+1,此时我们只需要比较 887. 鸡蛋掉落*** - 图8887. 鸡蛋掉落*** - 图9,取较小的那个对应的位置作为 x 即可。

这样一来,对于给定的状态 (k,n),我们只需要 O(logn) 的时间,通过二分查找就能得到最优的那个 x,因此时间复杂度从 O(kn^2) 降低至 O(knlogn),可以通过本题。

  1. class Solution {
  2. int[][] memo;
  3. public int superEggDrop(int k, int n) {
  4. memo = new int[k + 1][n + 1];
  5. for(int i = 0; i <= k; ++i){
  6. Arrays.fill(memo[i], -1);
  7. }
  8. return dp(k, n);
  9. }
  10. private int dp(int k, int n){
  11. if(memo[k][n] == -1){
  12. if(n == 0){
  13. memo[k][n] = 0;
  14. }else if(k == 1){
  15. memo[k][n] = n;
  16. }else{
  17. int left = 1, right = n;
  18. while(left + 1 < right){
  19. int x = left + (right - left)/2;
  20. int t1 = dp(k - 1, x - 1);
  21. int t2 = dp(k, n - x);
  22. if(t1 > t2){
  23. right = x;
  24. }else if(t1 < t2){
  25. left = x;
  26. }else{
  27. left = right = x;
  28. }
  29. }
  30. // 当前一次操作加DP
  31. memo[k][n] = 1 + Math.min(Math.max(dp(k - 1, left - 1), dp(k, n - left)), Math.max(dp(k - 1, right - 1), dp(k, n - right)));
  32. }
  33. }
  34. return memo[k][n];
  35. }
  36. }
  • 时间复杂度 O(knlog n)
  • 空间复杂度 O(kn)