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
Solution:
class Solution {
Integer[][] dp;
public int superEggDrop(int K, int N) {
dp = new Integer[K + 1][N + 1];
return helper(K, N);
}
private int helper(int k, int n) {
if (k == 1) return n;
if (n == 0) return 0;
if (dp[k][n] != null) return dp[k][n];
int res = n;
// for (int i = 1; i <= n; i ++) {
// res = Math.min(Math.max(helper(k - 1, i - 1), helper(k, n - i)) + 1, res);
// }
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
int broken = helper(k - 1, mid - 1);
int notBroken = helper(k, n - mid);
if (broken < notBroken) {
res = Math.min(res, notBroken + 1);
left = mid + 1;
} else {
res = Math.min(res, broken + 1);
right = mid - 1;
}
}
return dp[k][n] = res;
}
}