887-super-egg-drop
Question
https://leetcode.com/problems/super-egg-drop/description/
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 <= 10000
Thought Process
- Brute Force with DP (TLE)
- We create an dp array to store the best moves for each eggs and floors combination, where dp[i][j] represents the moves for i eggs and j floors
- For current eggs and floors, the best moves is obtained by dropping the egg from 1st floor up to current floor
- The minimum of all these drop tests are our answer
- For each test on ith floor, ranges from 1 to current floor, the egg could either break, so we need to use less egg on remaining floor dp[curEgg - 1][i - 1], or it doesn't, so we use dp[curEgg][curFloor - i]
- Because we are expecting worst case, the maximum of them + 1 (current egg drop) is the answer for dropping at ith floor
- Time complexity O(KN^2)
- Space complexity O(KN)
- DP with Binary
- Notice the function dp( K - 1, i - 1) increases when i increase, while on the other hand, dp(K, N - i) decreases when i increase
- We can use this observation to speed up the search for minimum i
- Time complexity O(KNlogN)
- Space complexity O(KN)
- DP with Optimality
- Looking at second function, the value increase when N increase, where the i_opt (current optimal) can be use as the starting point for next N
- Time complexity O(KN)
- Space complexity O(KN)
- DP with Problem Rephrase
- Instead of asking how many moves, we rephrase the question into how many floor we can cover for m moves, and K egg
- We create dp array, where dp[m][k] stores the floors that we can cover using m moves and k eggs
- For a floor X, when we drop the egg, there are two cases happen here
- If the egg breaks, we need to go down to check dp[m - 1][k - 1], we cover dp[m - 1][k - 1] + 1 + Y (top of X) floors
- Else If the egg doesn't break, we go up and check dp[m - 1][k], we cover X + dp[m -1][k] floors
- Where we can summarize into dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
- Time complexity O(KlogN)
- Space complexity O(KN)
- DP above - 1D
- We can reduce the space to O(k)
- Since dp[m][k] depends on the last row only, we can use dp[K+1] to store all the information
- Instead going from forward, we need to travel from backward in order to avoid using the updated value
- Time complexity O(KlogN)
- Space complexity O(K)
Solution
class Solution {
public int superEggDrop(int K, int N) {
int[][] memo = new int[K + 1][N + 1];
// define memo[i][j] to be the number of moves for i eggs and j floors
return dp(memo, K, N);
}
private int dp(int[][] memo, int K, int N) {
if (N <= 1) return 1;
if (K == 1) return N;
if (memo[K][N] > 0) return memo[K][N];
// now for current K and N, the problem can break down into dropping eggs
// from i = [1, N] floors.
// For each floor, the egg either breaks so we use less egg for remaining floor
// dp[K - 1][i - 1] or it doesn't that we use dp[K][N - i]. For each case, we
// are expecting the worst cast, so the max of them + 1 will be compared with
// current answer;
int res = Integer.MAX_VALUE;
for (int i = 1; i <= N; i++) {
res = Math.min(res, Math.max(dp(memo, K - 1, i - 1), dp(memo, K, N - i)) + 1);
}
memo[K][N] = res;
return res;
}
}
class Solution {
public int superEggDrop(int K, int N) {
int[][] memo = new int[K + 1][N + 1];
// define memo[i][j] to be the number of moves for i eggs and j floors
return dp(memo, K, N);
}
private int dp(int[][] memo, int K, int N) {
if (N <= 1) return 1;
if (K == 1) return N;
if (memo[K][N] > 0) return memo[K][N];
int res = N;
int lo = 1, hi = N;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
int breakMove = dp(memo, K - 1, mi - 1);
int safeMove = dp(memo, K, N - mi);
res = Math.min(res, Math.max(breakMove, safeMove) + 1);
if (breakMove == safeMove) break;
else if (breakMove > safeMove) hi = mi;
else lo = mi + 1;
}
memo[K][N] = res;
return res;
}
}
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K + 1][N + 1];
for (int j = 1; j <= N; j++) {
dp[1][j] = j;
}
for (int k = 2; k <= K; k++) {
int x = 1;
for (int n = 1; n <= N; n++) {
while (x < n && Math.max(dp[k - 1][x - 1], dp[k][n - x]) > Math.max(dp[k -1][x], dp[k][n - x -1])) x++;
dp[k][n] = 1 + Math.max(dp[k - 1][x - 1], dp[k][n - x]);
}
}
return dp[K][N];
}
}
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[N + 1][K + 1];
int m = 0;
while (dp[m][K] < N) {
m++;
for (int k = 1; k <= K; k++) {
dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1;
}
}
return m;
}
}
class Solution {
public int superEggDrop(int K, int N) {
int[] dp = new int[K + 1];
int m = 0;
while (dp[K] < N) {
m++;
for (int k = K; k > 0; k--) {
dp[k] += dp[k - 1] + 1;
}
}
return m;
}
}