[0887] 鸡蛋掉落

• GitHub
• http://leetcode.xuezhisd.top/post/469138e6.html
• https://leetcode.com/problems/super-egg-drop
• https://leetcode-cn.com/problems/super-egg-drop

题目描述

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

示例 2：

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

示例 3：

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

 

提示：

1. 1 <= K <= 100
2. 1 <= N <= 10000

Related Topics

数学

二分查找

动态规划

题目解析

• 可以使用动态规则的思路去解决本题，加上细节优化，这是动态规则类题目比较常见的一种考查模式，大致方法正确但是普通做法复杂度有点高，要通过其他知识进行优化。

不确定性

• 本题的题意和条件非常明确。
• 结果应该是最坏情况下的最小移动次数。

方法一：双指针查找

分析

• 对于确定的k,n 来说答案是固定的，那么我们不妨设解为dp(k, n)。
• 那么我们先考虑第一个鸡蛋应该在哪一层掉下，无非是2种结果(碎了和不碎)，可以根据结果转移到新的k’,n’。
• 以上分析可以看出这题非常适合使用动态规则来做。

思路

• 设dp(i, j) 为有i个鸡蛋，j层楼时确定F所需要的小移动次数。
• 显然，dp(1, j) = j, 此时只有一只鸡蛋所以一层一层试(0层不需要试，也是符合题意的)。 dp(i, 1) = 1 (i>=1), 只有一层试一次就够了。
• 接下来讨论j>1, i>1的情况。我们先拿一个鸡蛋放在x(1=<x<=j)层掉下，有2种情况
• 蛋碎了，说明再往上的都不行，楼层要下降，鸡蛋减少1个，结果是 1+dp(i-1, x-1)
• 蛋没碎，说明再往下都不会破，楼层要上升，鸡蛋保持原有数量，结果是1+dp(i, j-x)
• 每次尝试取最坏的结果 max{1+dp(i-1, x-1), 1+dp(i, j-x)}, 一共尝试j次，取其中的最好结果
• dp(i,j) = min{max{1+dp(i-1, x-1), 1+dp(i, j-x)}} (1=<x<=j)

superEggDrop(K,N){	
	for (int j=1;j<=N;++j) dp[1][j]=j;
  for(int i=1;i<=K;++i) dp[i][1] = 1;
  for(int i=2;i<=K;++i) {
    for(int j=2;j<=N;++j) {
      for(int x=1;x<=j;++x){
       	dp[i][j] = min (dp[i][j], max(1+dp[i-1][x-1], 1+dp[i], [j-x]))
      }
    }
	}
	
	return dp[K][N]
}

• 从上面代码中可以看出，有3重循环，对于 k=100, N=10000来说，显然是要超时。时间复杂度太高，需要优化。

• 

• 我们用上图表示dp中的2行，首先分析一下dp矩阵的值的规律，红色箭头表示，对于同等数量的鸡蛋，尝试次数会随着楼层呈现非递减。对于同一楼层，尝试次数会随着鸡蛋呈现非递减。

• 基于上述分析，现在要求解dp(i+1,j) = min{max{1+dp(i, x-1), 1+dp(i+1, j-x)}} (1=<x<=j)，其实是要找到一个p1(p1=x-1), p2(p2=j-x)使得dp(i, p1), dp(i+1, p2)差值最小。
• 这里要说明一下p1肯定是<=p2的是，如果p2=dp(i, p1-1), dp(i+1, p2)>=dp(i, p1-1)。当p1-1=p2+1时，dp(i+1, p2+1)最多比dp(i,p1-1)大1且 dp(i, p1)>=dp(i,p1-1) 。上述2种情况都不会比p1<=p2更优。
• 现在假设j=4时，找到了p1, p2使得最优解成立，现在j增加到5了，那么只要把p2变成p3继续与p1比较即可。分析如下：
• 由于dp(i, p1)<=dp(i+1, p2)<=dp(i+1, p3), 所以p3越往后，整体的值肯定是越大的，就没必要往后找了。往中间移动即可。

优化后思路
superEggDrop(K,N){	
	for (int j=1;j<=N;++j) dp[1][j]=j;
  for(int i=1;i<=K;++i) dp[i][1] = 1;
  for(int i=2;i<=K;++i) {
      int p1=0, p2=0;
      for(int j=2;j<=N;++j) {
        p2++;
        for(;p1+1<=p2-1 && dp[i-1][p1+1]<=dp[i][p2-1];p1++, p2--); //尽量往中间移动，使得差值越小越好
        dp[i][j] = dp[i][p2]+1;  
  		}
	}
	
	return dp[K][N]
}

• 里面的p1, p2 对于一个i循环来说最多移动N次，总体时间复杂度是O(k*n)

注意

知识点

• 动态规则
• 复杂度优化

复杂度

• 时间复杂度O(k*n)
• 空间复杂度O(k*n)

代码

//
class Solution {
private:
    void outDp(vector<vector<int> > dp) {
        for (auto v : dp) {
            for(auto d:v){
                printf("%3d", d);
            }
            cout<<endl;
        }
    }
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K+1, vector<int>(N+1, 0));

        for (int j=1;j<=N;++j) dp[1][j]=j;
        for(int i=1;i<=K;++i) dp[i][1] = 1;

        for(int i=2;i<=K;++i) {
            int p1=0, p2=0;
            for(int j=2;j<=N;++j) {
                p2++;
                for(;p1+1<=p2-1 && dp[i-1][p1+1]<=dp[i][p2-1];p1++, p2--);
                dp[i][j] = dp[i][p2]+1;

                //cout<<endl;
            }
        }
        //outDp(dp);

        return dp[K][N];
    }
};
/*
 1
 1
 3
200
3
80
1
2
4
230
100
10000
 */

相关题目