題目
略
答案
這個答案Leetcode TLE了均践，但是面試?yán)锩婵梢哉f剧罩。
class Solution {
public int superEggDrop(int K, int N) {
int[][] f = new int[N + 1][K + 1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
if(i == 1) {
f[i][j] = 1;
continue;
}
if(j == 1) {
f[i][j] = i;
continue;
}
int min = Integer.MAX_VALUE;
for(int x = 1; x <= i - 1; x++) {
// Try to drop an egg on any floor below floor i
// It may not break, then f[i - x][j] is a candidate for f[i][j]
// it may break, then f[x - 1][j - 1] is a candidate for f[i][j]
// we want to take the max of the two candidates for worst case consideration
// but we also want to find what's the minimum number of attempts, so we take
// a minimum of all the maximums generated
int max = Math.max(f[i - x][j], f[x - 1][j - 1]) + 1;
min = Math.min(min, max);
}
f[i][j] = min;
}
}
return f[N][K];
}
}
