leetcode887super-egg-drop扔鸡蛋问题中的逆向思维

发表于 | 分类于 ， |

之前在家里带宝宝之余，也刷了一些有意思的leetcode题目，把他们记录下来也是有意义的。
这里是887 扔鸡蛋问题的基本描述：
给你k个鸡蛋，可以使用这些鸡蛋对1到n共n层楼的每一层扔下，在这些楼层中第f层扔下时鸡蛋会碎，我们需要在不知道f的情况下，最少做多少次测试能确定鸡蛋刚好会碎的楼层f. 因为f不确定，我们的答案需要保证在最坏的情况下，最高效的检测方案。

1.问题描述

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
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?



Example 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.
Example 2:

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

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

2.基本示例分析

  • 如果有1个鸡蛋，2层楼， 答案为2
    分析：因为只有一个鸡蛋，由于f不确定，我们只能从第1层依次向上做测试,因为最坏的情况下，鸡蛋在第2层才能知道检测结果，所以答案是2

  • 如果有两个鸡蛋，6层楼，答案为3
    分析：2个鸡蛋的情况下，最少测试次数为k的情况下，需要满足如下： k + k-1 + … + 1 >= 6,可以得到答案，最小的k为3。这个计算公式是怎么来的呢，假设最少次数为k,表示每次尝试都有两种可能，要么碎，要么不碎，如果要在第一次碎的楼层f不确定的情况下，保证最少的检测次数，就要让每次检测碎与不碎的情况下，尝试的结果都比较均匀。如果每次测试鸡蛋都碎了。

    • 第1次抛在t层：
      如果碎了，因为还剩一个鸡蛋，子问题就变成了1个鸡蛋测试t-1楼； 加起来总共需要t次（t <=k ,因为如果t大于k,表明k并不是解)

    • 第一次抛没有碎：
      则进行第二次抛，此时考虑到第二次可能会碎，而此时还剩k-1次抛的机会，所以第二次需要从t + k -1 层开始抛. 如果第2次碎了，则不用继续向上，直接用剩下到一个鸡蛋对下面到 k-2层进行测试；总共需要k次

    • 如果第二次没有碎：
      此时已经顺利检测了t + k-1层，还剩k-2次抛的机会。 所以第三次可以从t + k-1 + k-2层开始抛；
      依此类推，如果一直不碎， 最后一次检测时候共可以检测 sum = t + k-1 + k-2 + … + 1层， 题目中楼高6层，则sum必须大于等于6才能保证一定覆盖完， 即t + k-1 + k-2 +…+ 1 >=6，有因为 k >= t ,得到 问题转换为求 k + k-1 + … + 1 >= 6,得到最小满足条件的k为3

3.通用算法分析

已经有了1个鸡蛋和2个鸡蛋的情况下问题的求解，那么怎么推广到k个鸡蛋n层楼到问题呢，其实在2个鸡蛋到问题分析中已经看出，这里是存在子问题的，第一反应就是动态规划，先保存子问题的解，然后推导状态转移方程楼。

3.1 思路1-直接思考

已知问题的解,这里用f(k,n)表示k个鸡蛋n层楼的最小可测试次数
k=1时，和楼层n相关f(1,n) = n
当k=2时，可以特殊分析，f(2,n) = { min(x) | x + x-1 +… +1 >=n} x(x+1) >= 2n

那3个鸡蛋n层楼的问题f(3,n)怎么解呢，因为状态转换右鸡蛋的碎与不碎引起，这里从鸡蛋状态入手假设最优解的第一个鸡蛋从t层drop，有两种情况
碎了： 则f(3,n) = f(2,t-1) + 1 ,表示用2个鸡蛋继续检测1到t-1层，t层以上不再需要检测
没碎： 则f(3,n) = f(3, n-t) +1 ，表示只有t+1到n共n-t层需要继续检测，t层以下不再需要检测。
为了保证检测到绝对覆盖，f(3,n)取两者到最大值，推广到k个鸡蛋，则f(k,n) = max (f(k-1, t-1) + 1, f(k, n-t) + 1 ) , 这里可以看出t的选择会影响最终结果的计算， k不变t变的情况下，f(k-1,t-1)单调递增，f(k,n-t)单调递减 1<= t <= n
所以，最终的状态转移方程如下：
f(k,n) = min(helper(k,n,t)) | 1<=t <=n
辅助函数： helper(k,n,t) = max(f(k-1,t-1)+1, f(k,n-t)+1)

如下是用golang实现的代码:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
func superEggDrop2(K int , N int) int {
    // dp[i][j]表示 i个鸡蛋 j层楼的最少测试次数
    dp := make([][]int, K+1)
	for i:=1; i<=K; i++ {
		dp[i] = make([]int, N+1)
	}
	//只有一个鸡蛋，按楼高更新
	for j:=1; j <=N; j++ {
		dp[1][j] = j
	}

	//如果楼高为1， 则需要1次
	for i:=1;i<=K;i++ {
		dp[i][1] = 1
	}
	var helper  func(int,  int) int
	helper = func(k int, n int) int {
		if n == 0 {
			return 0
		}
		if k > n {
			return helper(n, n)
		}
		if dp[k][n] != 0 {
			return dp[k][n]
		}

		min := n
		for t:= 1; t<=n; t++{
			// if drop egg broke, check lower floor
			brokeCase := helper(k-1,t-1) + 1
			// if not break, check upper floor
			safeCase := helper(k, n-t) + 1

			curMax := brokeCase
			if safeCase > curMax {
				curMax = safeCase
			}

			curRes := curMax
			if curRes < min {
				min = curRes
			}
		}

		return min
	}

	return helper(K, N)
}

3.2 思路2-逆向思考

在思路1的状态转移方程里，因为每次都确定第一次drop的楼层t,所以会需要把所有的情况都做一次计算，然后取最小值。整体运行下来的效率并不高,当数据量加大，会有运行超时的情况出现。 这里我们换个思路，在思路1的状态转移方程中，自变量是鸡蛋个数k和楼层高度n， 这次我们换个思路，在最优策略的情况下，我们能保证测试的楼层高度是和鸡蛋个数和drop个数有正相关的
这里我们可以逆向思考以下，用一个方程dp(k,d)表示还有k个鸡蛋和d次drop机会的情况下，我们能够覆盖的测试楼层数

状态转移分析：
如果第d次drop鸡蛋没有碎，则还剩k鸡蛋和d-1次drop的机会，后面的测试方向是向更高的楼层。
如果第d次鸡蛋碎了，则还剩下k-1和鸡蛋和d-1次drop的机会，后面的测试需要在更低的楼层进行

dp(k,d) = dp(k,d-1) + 1 + dp(k-1,d-1)
初始情况：
当k=1即只有一个鸡蛋的情况下，测试覆盖楼层数等于 drop机会次数d: dp(1,d) = d
当d=0即无drop机会的时候，测试覆盖楼层数为0

基于状态转移方程的问题求解：
将dp(k,d)的解存入一个二维数组，比如求4个鸡蛋14层测试楼层最少需要多少次drop的问题， 我们可以遍历 dp[4][0]到dp[4][i]，知道找到第一个大于等于14的下标i，即表示最少的drop次数

golang代码：

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
38
39
40
41
42
43
44
45
46
47
48
//superEggDrop的运行时间复杂度比superEggDrop2要好很多，同时状态转移方程也更清晰
func superEggDrop(K int, N int) int {
	dp := make([][]int, K+1) //dp[i][j] 表示i鸡蛋，j次drop可以确定的楼层数
	for i := 0; i <= K; i++ {
		dp[i] = make([]int, N+1)
		// for j := 0; j <= N; j++ {
		// 	dp[i][j] = -1
		// }
	}

	dp[0][0] = 0
	if K == 0 || N == 0 {
		return 0
	}
	if K == 1 {
		return N
	}
	//如果只有一个鸡蛋，dp[1][j]均初始化为drop次数j
	for i := 0; i <= N; i++ {
		dp[1][i] = i
		dp[0][i] = 0
	}

	//如果drop次数为0，则可检测楼数为0
	for i := 0; i <= K; i++ {
		dp[i][0] = 0
	}

	for i := 1; i <= K; i++ {
		for j := 1; j <= N; j++ {
			dp[i][j] = dp[i-1][j-1] + 1 + dp[i][j-1]
			if dp[i][j] >= N {

				// fmt.Println("i,j", i, j)
				break
			}
		}
	}
	fmt.Println("dp:", dp)
	for j := 1; j <= N; j++ {
		if dp[K][j] >= N {
			return j
		}
	}

	return N

}

小结

很多时候对数据模型的定义决定了处理逻辑的清晰成都，在处理动态规划类型的问题时，这个表现得也很明显，一个好的数据集定义，附带了更简洁清晰的数据转换。反过来说，正确理解数据变换的因果关系，找到合适的自变量和因变量，必然会带来更合适的数据定义。