You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.
You know that there exists a floor f where 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 unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.
Return the minimum number of moves that you need to determine with certainty what the value of f is.
Example 1:
Input: k = 1, n = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Example 2:
Input: k = 2, n = 6
Output: 3
Example 3:
Input: k = 3, n = 14
Output: 4
Constraints:
- 1 <= k <= 100
- 1 <= n <= 104
会超时
import java.lang.Math;
class Solution {
public int superEggDrop(int K, int N) {
int[][] memo = new int[K + 1][N + 1];
return helper(K, N, memo);
}
private int helper(int K, int N, int[][] memo) {
if (N <= 1) {
return N;
}
if (K == 1) {
return N;
}
if (memo[K][N] > 0) {
return memo[K][N];
}
int min = N;
for (int i = 1; i <= N; i++) {
// 鸡蛋碎了，从i层以下尝试，有i-1层
int left = helper(K - 1, i - 1, memo);
// 鸡蛋没碎，从i层以上尝试，有N-i层
int right = helper(K, N - i, memo);
min = Math.min(min, Math.max(left, right) + 1);
}
memo[K][N] = min;
return min;
}
}优化
import java.lang.Math;
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K+1][N+1];
// 初始化数组，存入最大值
for(int k=0;k<=K;k++){
for(int n=0;n<=N;n++){
dp[k][n] = Integer.MAX_VALUE;
}
}
for(int i=0;i<=N;++i){
// 0个鸡蛋, 最优值就是0
dp[0][i] = 0;
// 1个鸡蛋就是尝试i次才可以，跟随楼的高度，从第一层开始尝试
dp[1][i] = i;
}
for(int i=0;i<=K;++i){
// 楼的高度为0是，最优值就是0
dp[i][0] = 0;
}
for(int k=2;k<=K;++k){
for(int n=1;n<=N;++n){
int l = 1, h = n, m = 0;
while(l<=h){
m = l + (h-l)/2;
// broke 坏了, not broke 没有坏
int b = dp[k-1][m-1], nb = dp[k][n-m];
if(b > nb){
h = m-1;
}else{
l = m+1;
}
dp[k][n] = Math.min(dp[k][n], Math.max(b, nb)+1);
}
// 在每一个楼层做一个尝试
// for(int i=0;i<=n;i++){
// 从每次尝试中选取一个最小值，从鸡蛋碎了和鸡蛋没碎中选取一个最大值，表示最坏的情况
// dp[k][n] = Math.min(dp[k][n], Math.max(dp[k-1][i-1], dp[k][n-i]) + 1);
// }
}
}
return dp[K][N];
}
}