LeetCode刷题：887. Super Egg Drop

LeetCode刷题：887. Super Egg Drop

原题链接：https://leetcode.com/problems/super-egg-drop/

You are given K eggs, and you have access to a building with N floors from 1 to N. 

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). 

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

题目大意是：

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

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

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

 

Example 1:（例1）

Input: K = 1, N = 2
Output: 2 
Explanation:
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty. 

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

Example 2:

Input: K = 2, N = 6
Output: 3
Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

题目分析

先把题目意思理解了。说实话，我反应慢，看了好久才稍稍理解了题目的意思。之后，在网上搜了关于这个问题的帖子，才更加了解了这个题目要求什么。（智商不够吧~）

题目的要求解读出来就是：最少需要多少次尝试， 才能保证在最坏的情况下，找到鸡蛋破碎的临界楼层。 

明确问题

题目要求是考虑 在策略可能遭遇的 最坏情况下，尝试次数最少。 这个地方有些绕，但是必须搞清楚。

举个例子， 如果你用二分法，第一次把鸡蛋从50层扔下去， 最坏的情况是临界层在49层， 第一个鸡蛋碎了，第二个鸡蛋必须得从第一层楼找起。 因此这种策略最坏情况下的尝试次数是50次， 如果你决定采用这个策略， 那你针对题目的答案就是50。

现在的目标是找到一个最优策略， 该策略所对应的最坏情况， 比其他策略所对应的最坏情况所需要尝试的次数都要少。
 

我们假设有100层楼，我们开始扔鸡蛋，先从那一层开始尝试呢？

选择一：随机选择楼层 （失败的策略）

100层时的情况：假设从100层扔下第一个鸡蛋会发生什么？无非有两种选择：碎或者不碎。

• 如果碎了，1个鸡蛋没有了，只剩下1个鸡蛋了，那么如果从99层扔下，碎了，就没有鸡蛋可扔了，1—98层的情况还不知道，任务没完成。如果恰巧没碎，算是运气，临界楼层就是99了。
• 如果没碎，那么可以测试101层了。

看来这种想法不成立。也许你会说，如果从100层扔下碎了，那你可以从1—99层一层一层尝试，从1层，到2层，到3层，...

要记得，要找出最小的次数。

我们把100换成任意楼层，例如75层，80层，或者50层，按照上述方法都是不行的。

选择二：二分法 （失败的策略）

有人说我们采用二分法。

例如，第一个鸡蛋在50层扔下，如果碎了，第二个鸡蛋从1-49逐层试验。为什么要逐层试验呢？而不继续二分法呢？这个问题的答案显而易见，你只剩一个鸡蛋了。如果继续二分法测试，某一次，鸡蛋碎了，你还有很多剩余的楼层没有测试。而你没有鸡蛋了。

如果没碎，第一个鸡蛋在75层扔下，如果碎了，第二个鸡蛋从51-74逐层试验…你可以算算，需要多少次测试？

二分法也似乎不是好的方法。

选择三：等分法（失败的的略，但是比之前的两种选择稍稍好一些）

有人说，等分法。将100层楼，按照每10层进行等分划分。每一份就是10层楼。

首先，将鸡蛋从第10层楼开始扔。那么结果有两种可能：

• 情况1：如果碎了，说明临界楼层在1到10之间，但现在只剩下一个鸡蛋了，只能从第一层一直到第10层。
• 情况2：如果没有碎，接下来从第20层扔鸡蛋。

该方法的思路是，用一个鸡蛋来试探，找到临界楼层的大致范围[1~10]、[11-20]….[91-100]。然后用另一个鸡蛋在大致范围内找出精确楼层。该方法的最坏次数是：18次。

看来尝试的次数减少了很多。还有没有更好地选择？

选择四：数学猜测法（设定X）

假设题目所要求的策略存在，该策略可以保证在最坏情况下至多需要扔 x 次鸡蛋就可以找出临界楼层。

此时可以将问题转化为：如果只允许扔 x 次鸡蛋能确定的最高的楼层是多少。现在思考， 第一次鸡蛋应该从哪个楼层扔下?

因为我们有两个鸡蛋， 为了在有限次数内检查尽可能高的楼层。 第一次扔的时候，我们会希望能尽可能高一些。如果鸡蛋没碎，我们就能排除掉越多的楼层。 但是很显然，又不能过高， 因为万一鸡蛋碎了，第二个鸡蛋就只能从第1层开始逐层尝试。
那么第一次扔的楼层最高可以选第几层呢？

答案就是 x 。 

因为我们总要考虑最坏情况， 当我们从 x 层扔下的时候， 最坏的情况有：

• 可能是临界层为 x-1, 此时就需要尝试 x 次，才能找到这个临界层。
• 如果第1次尝试的楼层比 x 大，显然会导致最大尝试次数超过x , 不符合我们的假设（我们的假设是尝试 x 次）。

现在假设了在最大尝试次数为x次时， 最优策略第1次必然只能从 x 层往下取值后， 我们最大能检查的楼层是多少？

由于第1次从 x 层扔下时， 我们已经用掉了1次尝试机会， 此时只能再尝试 x-1 次。 这样我们可以第二次尝试的楼层数可以向上增加 x-1层， 即为 x + (x-1)。
如果再高，例如，第2次我们从 2x 层扔下， 我们在最坏情况下（临界楼层为 2x-1），需要尝试的次数会变成 x+1, 不符合我们的假设。

这样依次类推， 第3次向上的增量就只能为 x-3, 第4次向上的增量就只能为 x-4, …….., 最后一次向上的增量为 1。

此时可以得出，如果只能尝试 x 次， 能检测的最高楼层为：

x + (x−1) + (x−2) + (x−3)....+1

等价于：(x∗(x+1)) / 2x+(x−1)+(x−2)+(x−3)....+1

等价于：(x∗(x+1)) / 2

此时答案就出来了， 我们有100层楼， 则有

x*(x+1)/2 >=100

解出来 x >= 14

即需要测试 14 次。

借鉴了别人的想法，自己想了很久才理解了。

 

算法分析

N 个eggs，K 代表楼层

递归算法：试着从每层楼，从1到K扔下一个鸡蛋，并计算出最坏情况下需要扔下的最小数量。

• Eggs — 1，Floors—x：从1楼开始扔鸡蛋，如果鸡蛋没有破，那么再从2楼扔，依次类推。所以，最坏的情况是，当x次以后可以找到可以扔破鸡蛋的楼层。
• Floors = 0：不用试
• Floors = 1：需要尝试
• 剩余的情况：如果鸡蛋从第x层扔下，只能存在两种情况：破或者不破
• 如果鸡蛋破了，check楼层是否小于x；所以问题是减少了 n-1个鸡蛋和 x-1层楼层
• 如果鸡蛋没破，check楼层是否大于x，并剩余了n个鸡蛋。所以问题是减少了n个鸡蛋和k-x层楼层

没有思路，先看看这里的解释：https://brilliant.org/wiki/egg-dropping/

 

算法设计

public int getDrops(int eggs, int floors) {
		// base case 1:
		// if floors = 0 then no drops are required OR floors = 1 then 1 drop is
		// required
		if (floors == 0 || floors == 1)
			return floors;

		// base case 2:
		// if only one egg is there then drops = floors
		if (eggs == 1)
			return floors;

		int minimumDrops = Integer.MAX_VALUE, tempResult;
		// check dropping from all the floors 1 to floors and pick the minimum among
		// those.
		// for every drop there are 2 scenarios - a) either egg will break b) egg will
		// not break
		for (int i = 1; i <= floors; i++) {
			// for the worst case pick the maximum among a) and b)
			tempResult = Math.max(getDrops(eggs - 1, i - 1), getDrops(eggs, floors - i));
			minimumDrops = Math.min(tempResult, minimumDrops);
		}
		return minimumDrops + 1;
	}

这个算法提交之后，Time Limit Exceeded！

---

 采用动态规划算法

public int superEggDrop(int K, int N) {
       int dp[] = new int [K+1],m=0;
         for(m=0;dp[K]<N;++m){
             for(int k = K;k>0;--k)
             dp[k]+=dp[k-1]+1;
         }
         return m;
}

这个算法提交之后，AC了。

 

完整测试代码如下：

package com.bean.algorithm.basic;

public class EggDropDP {
	
	 public int superEggDrop(int K, int N) {
	       int dp[] = new int [K+1],m=0;
	         for(m=0;dp[K]<N;++m){
	             for(int k = K;k>0;--k)
	             dp[k]+=dp[k-1]+1;
	         }
	         return m;
	    }

	public static void main(String[] args) {
		EggDropDP eggDropDP = new EggDropDP();
		int eggs = 2;
		int floors = 10;
		System.out.printf("(DP) Minimum number of drops required in worst case with eggs: " + eggs
				+ " and floors:" + floors + " is: " + eggDropDP.superEggDrop(eggs, floors));
	}
}

---

另外一种AC的JAVA代码，从LeetCode上摘抄的，学习一下！

	public int superEggDrop(int K, int N) {
		if (N <= 0) {
			return 1;
		}
		if (K <= 1) {
			return N;
		}
		List<List<Integer>> nodes = new ArrayList<>();
		// Initialize DP table for K = 1
		for (int k = 0; k < K - 1; k++) {
			List<Integer> list = new ArrayList<>();
			list.add(1);
			nodes.add(list);
		}
		int level = 0; // Current level
		int sum = 1; // Total number of nodes in the K-Tree up to current level
		while (sum < N) {
			nodes.get(0).add(nodes.get(0).get(level) + 1);
			for (int k = 1; k < K - 1; k++) {
				nodes.get(k).add(nodes.get(k - 1).get(level) + nodes.get(k).get(level));
			}
			level++;
			sum += nodes.get(K - 2).get(level);
		}
		return level + 1;

	}

提交AC

---

动态规划思路

第一次尝试的楼层， 会对最终的结果产生直接的影响。

现在 设 f(m, n) 为m个鸡蛋， n层楼时， 在最坏情况下的最少尝试次数。

如果第一次尝试从 x 层楼开始， 则 f(m,n)=1+max(f(m−1,x−1)，f(m,n−x))
f(m−1,x−1) 对应的是第一次尝试鸡蛋被摔碎的情况
f(m,n−x) 对应的是第一次尝试鸡蛋没被摔碎的情况
接下来，只需要编写动态规划程序， 将每一种 x 都尝试一次， 计算出最小的结果即可。

package com.bean.algorithm.basic;

public class EggDropDP2 {

	public static void main(String[] args) {
		int floors = 100;
		int eggs = 2;

		System.out.println(superEggDrop(eggs, floors));
	}


	private static int superEggDrop(int eggs, int floors) {
		int table[][] = new int[eggs + 1][floors + 1];

		// boundary condition:
		// if no floors or 1 floors, only need 0 trails or 1 trails

		for (int i = 0; i <= eggs; i++) {
			table[i][1] = 1;
			table[i][0] = 0;
		}

		// if only one egg, f(1,k) = k

		for (int j = 0; j <= floors; j++) {
			table[1][j] = j;
		}

		// for the rest of cases
		// f( eggs, floors) = 1+ Max(f( eggs-1 , floors-1), f( eggs, floors-x))
		// x is the floor number we choose to drop for current attempt
		// range of i = 1,2,.....,floors,
		for (int i = 2; i <= eggs; i++) {
			for (int j = 2; j <= floors; j++) {

				table[i][j] = Integer.MAX_VALUE; // so important

				for (int floorTriedFirst = 1; floorTriedFirst <= j; floorTriedFirst++) {
					int res = 1 + Math.max(table[i - 1][floorTriedFirst - 1], table[i][j - floorTriedFirst]);
					if (res < table[i][j]) {
						table[i][j] = res;
					}
				}

			}
		}

		return table[eggs][floors];
	}

}

这个算法，可以得到正确的答案。

但是在LeetCode上提交，仍然是 Time Limit Exceeded！