You are given K eggs, and you have access to a building with N floors from 1 to N.
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 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 egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
Note:
- 1 <= K <= 100
- 1 <= N <= 10000
超时的解决方法
import java.lang.Math;
class Solution {
public int superEggDrop(int K, int N) {
int dp[][] = new int[N+2][K+2];
dp[0][0] = 0;
for(int i=1;i<=N;i++){
dp[i][0] = 0;
for(int k=1;k<=K;k++){
dp[i][k] = dp[i-1][k-1] + dp[i-1][k] + 1;
if(dp[i][k] >= N){
return i;
}
}
}
return N;
}
}最好的解决方法
class Solution {
public int superEggDrop(int n, int k) {
int [][] dp = new int[n+1][k+1];
int m = 0;
while (dp[n][m] < k) {
m += 1;
for (int egg=1; egg<=n; egg++) {
dp[egg][m] = dp[egg][m-1] + dp[egg-1][m-1] + 1;
}
}
return m;
}
}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];
}
}- Accepted
class Solution {
public int superEggDrop(int n, int k) {
int [][] dp = new int[n+1][k+1];
int m = 0;
while (dp[n][m] < k) {
m += 1;
for (int egg=1; egg<=n; egg++) {
dp[egg][m] = dp[egg][m-1] + dp[egg-1][m-1] + 1;
}
}
return m;
}
}- Time limit exceeded.
class Solution {
public int superEggDrop(int n, int k) {
int [][] dp = new int [n+1][k+1];
int result;
for (int i=1; i<=n; i++) {
dp[i][1] = 1;
dp[i][0] = 0;
}
for (int j=1; j<=k; j++) {
dp[1][j] = j;
}
for (int i=2; i<=n; i++) {
for (int j=2; j<=k; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int floors=1; floors<=j; floors++) {
result = 1 + Math.max(dp[i-1][floors-1], dp[i][j-floors]);
dp[i][j] = Math.min(result, dp[i][j]);
}
}
}
return dp[n][k];
}
}方法一：dp[i][j]表示剩余i个鸡蛋处理j层楼至少要扔几次，那么怎么推理dp[i][j]呢？枚举第一个鸡蛋扔的楼层（1～j）,假设扔到了第k层，碎了，转移到dp[i-1][k-1];没碎，转移到dp[i][j-k]。结果就是这两种情况，因为要保证找出临界点，我们必须假设最坏情况即max(dp[i-1][k-1], dp[i][j-1])，但是第一个鸡蛋我不一定扔在第K层，我选一个最优的楼层去扔也就是min(max(dp[i-1][k-1], dp[i][j-1])) （1<=k<=j），然后就搞定了，复杂度O(knn)，结果对但是会超时。
方法二：参考别人的牛逼思路，dp[i][j]表示i个鸡蛋扔j次至多能测出多少层的楼（换个说法：临界点已知在这么多层楼之内的话，i个蛋扔j次肯定能找出来）。怎么推dp[i][j]呢？也是考虑第一个蛋扔的位置，你会扔在哪里？假如扔在特别高的楼层，第10000000000......层，万一它碎了，它就白白的碎了，没有为剩下的i-1个蛋，j-1次操作作贡献。所以第一次扔的楼层应该是第dp[i-1][j-1]+1楼，为什么呢？因为这样即使它碎了，剩下的i-1个蛋肯定要往楼下扔，而dp[i-1][j-1]便是它们能发挥的最大作用楼层（物尽其用）;如果它没碎肯定要往楼上扔，那就是dp[i][j-1]了。总结就是dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1了，复杂度O(k*n)。这刚好是杨辉三角，容易整型溢出，编码注意for循环的顺序。
class Solution {
public:
int dp[101][10001];
int superEggDrop(int K, int N) {
for(int j=1; j<=N; ++j){
for(int i=1; i<=K; ++i){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1;
if(dp[i][j] >= N)
return j;
}
}
return N;
}
};