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 <= K <= 100
1 <= N <= 10000

题目大意

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

提示：

1 <= K <= 100
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)。
{{< katex display >}} dp(K,N) = MIN \begin{bmatrix} , , MAX(dp(K-1,X-1),dp(K,N-X)), , \end{bmatrix} ,1\leqslant x \leqslant N \ {{< /katex >}}
换个角度来看这个问题，定义 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) 为 t 和 k 的函数，题目所要求能测到最大楼层是 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。有状态转移方程得：
{{< katex display >}} \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} {{< /katex >}} 令 g(t,k) = f(t,k) - f(t,k-1)，可以得到：
{{< katex display >}} g(t,k) = g(t-1,k) + g(t-1,k-1) {{< /katex >}} 可以知道 g(t,k) 是一个杨辉三角，即二项式系数： {{< katex display >}} g(t,k) = \binom{t}{k+1} = C_{t}^{k+1} {{< /katex >}}
利用裂项相消的方法： {{< katex display >}} \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} {{< /katex >}}
于是可以得到：
{{< katex display >}} \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} {{< /katex >}} 其中：
{{< katex display >}} \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} {{< /katex >}} 于是针对每一项的二项式常数，都可以由前一项乘以一个分数得到下一项。
{{< katex display >}} \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} {{< /katex >}} 利用二分搜索，不断的二分 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
}