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
public class Solution {
/**
* @param m the number of eggs
* @param n the umber of floors
* @return the number of drops in the worst case
*/
int dropEggs2(int m, int n) {
// Write your code here
int[][] state = new int[n + 1][m + 1];
for (int i = 1; i < m + 1; i++) {
state[1][i] = 1;
}
for (int i = 1; i < n + 1; i++) {
state[i][1] = i;
}
for (int i = 2; i < n + 1; i++) {//n ---> floor
for (int j = 2; j < m + 1; j++) {//m ---> eggs
int min = Integer.MAX_VALUE;
for (int k = 1; k < i + 1; k++) {
min = Math.min(Math.max(state[k - 1][j - 1], state[i - k][j]),min);
}
state[i][j] = min + 1;
}
}
return state[n][m];
}
//f[t][p] = min(max(f[s - 1][p - 1]),f[t - s][p])|s=1...t) + 1
//总共t层，在s层扔p个蛋
}