0887. Super Egg Drop

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

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

Note:

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

题目大意 #

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

提示:

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

解题思路 #

  • 给出 K 个鸡蛋,N 层楼,要求确定安全楼层 F 需要最小步数 t
  • 这一题是微软的经典面试题。拿到题最容易想到的是二分搜索。但是仔细分析以后会发现单纯的二分是不对的。不断的二分确实能找到最终安全的楼层,但是这里没有考虑到 K 个鸡蛋。鸡蛋数的限制会导致二分搜索无法找到最终楼层。题目要求要在保证能找到最终安全楼层的情况下,找到最小步数。所以单纯的二分搜索并不能解答这道题。
  • 这一题如果按照题意正向考虑,动态规划的状态转移方程是 searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) )。其中 X 是丢鸡蛋的楼层。随着 X[1,N],都能计算出一个 searchTime 的值,在所有这 N 个值之中,取最小值就是本题的答案了。这个解法可以 AC 这道题。不过这个解法不细展开了。时间复杂度 O(k*N^2)
    \[ dp(K,N) = MIN \begin{bmatrix} \, \, MAX(dp(K-1,X-1),dp(K,N-X))\, \, \end{bmatrix} ,1\leqslant x \leqslant N \\\]
  • 换个角度来看这个问题,定义 dp[k][m] 代表 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] + 1 + dp[k][t-1] 层楼。
  • 在所有 m 步中只要有一次出现了第一种情况,那么我们就可以求解无限高的楼层。但题目要求我们能保证一定能找到安全楼层,所以每次丢鸡蛋的情况应该按照最差情况来,即每次都是第二种情况。于是得到转状态转移方程: dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 。这个方程可以压缩到一维,因为每个新的状态只和上一行和左一列有关。那么每一行从右往左更新,即 dp[i] += 1 + dp[i-1]。时间复杂度 O(K * log N),空间复杂度 O(N)
  • 可能会有人有疑问,如果最初选择不在 dp[k-1][t-1] + 1 层丢鸡蛋会怎么样呢?选择在更低的层或者更高的层丢鸡蛋会怎样呢?
    1. 如果在更低的楼层丢鸡蛋也能保证找到安全楼层。那么得到的结果一定不是最小步数。因为这次丢鸡蛋没有充分的展现鸡蛋和移动次数的潜力,最终求解一定会有鸡蛋和步数剩余,即不是能探测的最大楼层了。
    2. 如果在更高的楼层丢鸡蛋,假设是第 dp[k-1][t-1] + 2 层丢鸡蛋,如果这次鸡蛋碎了,剩下 k-1 个鸡蛋和 t-1 步只能保证验证 dp[k-1][t-1] 的楼层,这里还剩 dp[k-1][t-1]+ 1 的楼层,不能保证最终一定能找到安全楼层了。
  • 用反证法就能得出每一步都应该在第 dp[k-1][t-1] + 1 层丢鸡蛋。
  • 这道题还可以用二分搜索来解答。回到上面分析的状态转移方程:dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 。用数学方法来解析这个递推关系。令 f(t,k)tk 的函数,题目所要求能测到最大楼层是 N 的最小步数,即要求出 f(t,k) ≥ N 时候的最小 t。由状态转移方程可以知道:f(t,k) = f(t-1,k) + f(t-1,k-1) + 1,当 k = 1 的时候,对应一个鸡蛋的情况,f(t,1) = t,当 t = 1 的时候,对应一步的情况,f(1,k) = 1。有状态转移方程得:
    \[ \begin{aligned} f(t,k) &= 1 + f(t-1,k-1) + f(t-1,k) \\ f(t,k-1) &= 1 + f(t-1,k-2) + f(t-1,k-1) \\ \end{aligned}\]g(t,k) = f(t,k) - f(t,k-1),可以得到:
    \[ g(t,k) = g(t-1,k) + g(t-1,k-1)\] 可以知道 g(t,k) 是一个杨辉三角,即二项式系数: \[ g(t,k) = \binom{t}{k+1} = C_{t}^{k+1}\]
    利用裂项相消的方法: \[ \begin{aligned} g(t,x) &= f(t,x) - f(t,x-1) \\ g(t,x-1) &= f(t,x-1) - f(t,x-2) \\ g(t,x-2) &= f(t,x-2) - f(t,x-3) \\ \begin{matrix} .\\ .\\ .\\ \end{matrix}\\ g(t,2) &= f(t,2) - f(t,1) \\ g(t,1) &= f(t,1) - f(t,0) \\ \end{aligned}\]
    于是可以得到:
    \[ \begin{aligned} f(t,k) &= \sum_{1}^{k}g(t,x) = \sum_{0}^{k} \binom{t}{x} \\ &= C_{t}^{0} + C_{t}^{1} + C_{t}^{2} + ... + C_{t}^{k} \\ \end{aligned}\] 其中:
    \[ \begin{aligned} C_{t}^{k} \cdot \frac{n-k}{k+1} &= C_{t}^{k+1} \\ C_{t}^{k} &= C_{t}^{k-1} \cdot \frac{t-k+1}{k} \\ \end{aligned}\] 于是针对每一项的二项式常数,都可以由前一项乘以一个分数得到下一项。
    \[ \begin{aligned} C_{t}^{0} &= 1 \\ C_{t}^{1} &= C_{t}^{0} \cdot \frac{t-1+1}{1} \\ C_{t}^{2} &= C_{t}^{1} \cdot \frac{t-2+1}{2} \\ C_{t}^{3} &= C_{t}^{2} \cdot \frac{t-3+1}{3} \\ \begin{matrix} .\\ .\\ .\\ \end{matrix}\\ C_{t}^{k} &= C_{t}^{k-1} \cdot \frac{t-k+1}{k} \\ \end{aligned}\] 利用二分搜索,不断的二分 t,直到逼近找到 f(t,k) ≥ N 时候最小的 t。时间复杂度 O(K * log N),空间复杂度 O(1)

代码 #


package leetcode

// 解法一 二分搜索
func superEggDrop(K int, N int) int {
	low, high := 1, N
	for low < high {
		mid := low + (high-low)>>1
		if counterF(K, N, mid) >= N {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// 计算二项式和,特殊的第一项 C(t,0) = 1
func counterF(k, n, mid int) int {
	res, sum := 1, 0
	for i := 1; i <= k && sum < n; i++ {
		res *= mid - i + 1
		res /= i
		sum += res
	}
	return sum
}

// 解法二 动态规划 DP
func superEggDrop1(K int, N int) int {
	dp, step := make([]int, K+1), 0
	for ; dp[K] < N; step++ {
		for i := K; i > 0; i-- {
			dp[i] = (1 + dp[i] + dp[i-1])
		}
	}
	return step
}


⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者