难度:
Hard
题意:
思路:
cache[K][N]
表示K个蛋在N层试验最少要试验的次数,假设第一次要在i层丢蛋,那么分成了两个子问题,如果蛋没碎了,那么最少次数等于cache[k][N-i]+1
,如果蛋碎了,那么最少次数等于cache[k-1][i-1]+1
cache[k][N] = min[1<=i<=N]{max{cache[k][N-i], cache[k - 1][i - 1] + 1} + 1}
,时间复杂度是o(kNN)cache[k][N]
是非严格递增输了,且递增值不会超过1,即0<=cache[k][i+1]-cache[k][i]<=1
cache[k][N]
最优解的i,跟cache[k][N+1]
最优解的j,关系是0<=j-i<=1
代码:
class Solution {
private static int[][] cache;
private static void init() {
if (cache == null) {
cache = new int[101][10001];
for (int i = 1;i <= 10000;i++) {
cache[1][i] = i;
}
for (int i = 2;i <= 100;i++) {
cache[i][1] = 0;
cache[i][1] = 1;
cache[i][2] = 2;
int idx = 1;
for (int j = 3;j <= 10000;j++) {
while (cache[i - 1][idx + 1] <= cache[i][j - idx - 2]) {
idx++;
}
cache[i][j] = Math.max(cache[i - 1][idx], cache[i][j - idx - 1]) + 1;
}
}
}
}
public int superEggDrop(int K, int N) {
init();
return cache[K][N];
}
}