如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 887. 鸡蛋掉落 谷歌微软经典题目

力扣原题链接(点我直达) (opens new window)

你将获得 K 个鸡蛋,并可以使用一栋从 1N 共有 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 是多少。
1
2
3
4
5
6
7

示例 2:

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

示例 3:

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

提示:

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

# 第0版 最好懂,可是会超时

int superEggDrop(int K, int N)
{
	if (N == 0 || N == 1 || K == 1) {
		return N;
	}

	int minNum = N;
	for (int i = 1; i <= N; i++) {
		int tMin = max(superEggDrop(K - 1, i - 1), superEggDrop(K, N - i));
		minNum = min(minNum, 1 + tMin);
	}
	return minNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 第一版,公众号解析

https://mp.weixin.qq.com/s/7PEBnUfIpiuw26lVeihlhA

# 第二版,换个思路解题

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.3 MB, 在所有 cpp 提交中击败了93.34%的用户

从多少楼层多少个蛋最少要扔几次,转变为有多少个蛋扔几次可以测试出多少楼层。

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.1 MB, 在所有 cpp 提交中击败了97.84%的用户

int help(int i, int K) {
	return (i == 1 || K == 1) ? i : help(i - 1, K - 1) + help(i - 1, K) + 1;
}


int superEggDrop(int K, int N) {
	int count = 1;
	while (help(count, K) < N) {
		count++;
	}
	return count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 第二版的第二种解释

上面的方法的思路,都还是顺着题目的思路的进行的,其实我们可以换一个思路来想:“求k个鸡蛋在m步内可以测出多少层”。我们令dp [k] [m]表示k个鸡蛋在m步内可以测出的最多的层数,那么当我们在第X层扔鸡蛋的时候,就有两种情况:

鸡蛋碎了,我们少了一颗鸡蛋,也用掉了一步,此时测出N - X + dp [k-1] [m-1]层,X和它上面的N-X层已经通过这次扔鸡蛋确定大于F; 鸡蛋没碎,鸡蛋的数量没有变,但是用掉了一步,剩余X + dp [k] [m-1],X层及其以下已经通过这次扔鸡蛋确定不会大于F; 也就是说,我们每一次扔鸡蛋,不仅仅确定了下一次扔鸡蛋的楼层的方向,也确定了另一半楼层与F的大小关系,所以在下面的关键代码中,使用的不再是max,而是加法(这里是重点)。评论里有人问到为什么是相加,其实这里有一个惯性思维的误区,上面的诸多解法中,往往求max的思路是“两种方式中较大的那一个结果”,其实这里的相加,不是鸡蛋碎了和没碎两种情况的相加,而是“本次扔之后可能测出来的层数 + 本次扔之前已经测出来的层数”。

假设我们有 k 个鸡蛋可以移动 m 步,考虑某一步 t 应该在哪一层丢鸡蛋?一个正确的选择是在 dp [k-1] [t-1] + 1 层丢鸡蛋,结果分两种情况:

  1. 如果鸡蛋碎了,我们首先排除了该层以上的所有楼层(不管这个楼有多高),而对于剩下的 dp [k-1] [t-1] 层楼,我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下,我们总共可以求解无限高的楼层。可见,这是一种非常好的情况,但并不总是发生。
  2. 如果鸡蛋没碎,我们首先排除了该层以下的 dp [k-1] [t-1] 层楼,此时我们还有 k 个蛋和 t-1 步,那么我们去该层以上的楼层继续测得 dp [k] [t-1] 层楼。因此这种情况下,我们总共可以求解 dp [k-1] [t-1] + dp [k] [t-1] + 1 层楼。

容易想象,在所有 m 步中只要有一次出现了第一种情况,那么我们就可以求解无限高的楼层。但“保证求解”的定义要求我们排除一切运气成分,因此我们只得认为每次移动都遇到第二种情况。于是得到递推公式:

dp [k ] [t] = dp [k-1] [t-1] + dp [k] [t-1] + 1

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :31.8 MB, 在所有 cpp 提交中击败了25.89%的用户

int superEggDrop(int K, int N)
{
	vector<vector<int>>  dp(K + 1,vector<int>(N + 1,0));
	//当N=0时,K等于多少都是0,或者当K=1时,只能有K种解法了
	//dp[0][m] = 0; // zero egg
	for (int n = 1; n <= N; n++) {
		for (int k = 1; k <= K; k++) {
			dp[k][n] = dp[k][n - 1] + dp[k - 1][n - 1] + 1;
			if (dp[k][n] >= N) {
				return n;
			}
		}
	}
	return N;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1