Drop Eggs II
There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.
You're given m eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.
Example:
Given m = 2, n = 100 return 14
Given m = 2, n = 36 return 8
Code:
public class Solution {
/**
* @param m the number of eggs
* @param n the umber of floors
* @return the number of drops in the worst case
*/
public int dropEggs2(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
//state: f[x][y] represents the minimum number of trials that needed for verifying the worst case of y floors with x eggs
int[][] f = new int[m + 1][n + 1];
//initialization:
//when there is only one egg
for (int i = 1; i <= n; i++) {
f[1][i] = i;
}
//when there is only one floor
for (int i = 1; i <= m; i++) {
f[i][1] = 1;
}
//function:
/* drop one egg (out of m) on any arbitrary floor k (out of n), there will be two cases:
* (1). egg - break, number of trials is reduced to subproblem(m - 1, k - 1)
* (2). egg - !break, number of trails is reduced to subproblem(m, n -k)
* The worst case amoung these two will be the total trials required after floor x
*/
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
f[i][j] = Integer.MAX_VALUE;
for (int k = 1; k < j; k++) {
int worstCase = Math.max(f[i - 1][k - 1], f[i][j - k]) + 1; // add one for current drop
f[i][j] = Math.min(f[i][j], worstCase); //find the minimum amoung these decisions
}
}
}
//answer:
return f[m][n];
}
}