website/content.en/ChapterFour/0800~0899/0887.Super-Egg-Drop.md
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 <= 1001 <= N <= 10000You are given K eggs and can use a building with floors from 1 to N, for a total of N floors. Each egg functions the same way, and if an egg breaks, you can no longer drop it. You know there exists a floor F such that 0 <= F <= N: any egg dropped from a floor higher than F will break, and any egg dropped from floor F or below will not break. Each move, you can take an egg (if you have an intact one) and drop it from any floor X (where 1 <= X <= N). Your goal is to know exactly what the value of F is. Regardless of the initial value of F, what is the minimum number of moves needed to determine the value of F?
Hints:
K eggs and N floors, determine the minimum number of moves t needed to find the safe floor F.K eggs into account. The limitation on the number of eggs may prevent binary search from finding the final floor. The problem asks us to find the minimum number of moves while guaranteeing that the final safe floor can be found. Therefore, simple binary search cannot solve this problem.searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) ). Here X is the floor from which the egg is dropped. As X ranges over [1,N], a searchTime value can be computed; among all these N values, the minimum is the answer to this problem. This solution can AC this problem. This solution will not be expanded in detail here. The time complexity is O(k*N^2).dp[k][m] as the maximum number of floors that can be checked with K eggs and M moves. Consider at which floor an egg should be dropped on some move t. A correct choice is to drop the egg at floor dp[k-1][t-1] + 1. There are two possible outcomes:
dp[k-1][t-1] floors, we can definitely solve the problem with k-1 eggs in t-1 moves. Therefore, in this case, we can solve for a building of infinite height in total. It can be seen that this is a very good situation, but it does not always occur.dp[k-1][t-1] floors below that floor. At this point we still have k eggs and t-1 moves, so we continue testing floors above that floor and can test dp[k][t-1] floors. Therefore, in this case, we can solve dp[k-1][t-1] + 1 + dp[k][t-1] floors in total.m moves, we can solve a building of infinite height. But the problem requires that we can guarantee finding the safe floor, so each egg-drop outcome should be considered in the worst case, that is, the second situation happens every time. Thus we obtain the state transition equation: dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 . This equation can be compressed to one dimension, because each new state only depends on the previous row and the column to the left. Then update each row from right to left, i.e. dp[i] += 1 + dp[i-1]. The time complexity is O(K * log N), and the space complexity is O(N).dp[k-1][t-1] + 1? What happens if we choose a lower floor or a higher floor?
dp[k-1][t-1] + 2. If the egg breaks this time, the remaining k-1 eggs and t-1 moves can only guarantee checking dp[k-1][t-1] floors, and floor dp[k-1][t-1]+ 1 is still left, so we can no longer guarantee that the safe floor can definitely be found.dp[k-1][t-1] + 1.dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 . Use mathematical methods to analyze this recurrence. Let f(t,k) be a function of t and k. The problem asks for the minimum number of moves needed to test up to a maximum floor of N, that is, to find the minimum t such that f(t,k) ≥ N. From the state transition equation, we know: f(t,k) = f(t-1,k) + f(t-1,k-1) + 1. When k = 1, corresponding to the case of one egg, f(t,1) = t; when t = 1, corresponding to the case of one move, f(1,k) = 1. From the state transition equation we get:g(t,k) = f(t,k) - f(t,k-1), and we can get:g(t,k) is Pascal's triangle, i.e. the binomial coefficient:
{{< katex display >}}
g(t,k) = \binom{t}{k+1} = C_{t}^{k+1}
{{< /katex >}}t until converging to the smallest t such that f(t,k) ≥ N. The time complexity is O(K * log N), and the space complexity is O(1).
package leetcode
// Solution 1: Binary search
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
}
// Calculate the binomial sum, with the special first term 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
}
// Solution 2: Dynamic programming 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
}