Title
https://www.lintcode.com/problem/584
There is an n-story building. If an egg falls from level k and above, it will break. If dropped from any level below this level, it will not break. There are m eggs, use the method with the least number of experiments in the worst case to find k, and return the number of experiments required in the worst case. Sample example 1: Input: m = 2, n = 100 Output: 14 Example 2: Input: m = 2, n = 36 Output: 8
Ideas
There are two methods, which are essentially the same. The first is recursive, which will time out but can produce results, and the second is dynamic programming.
The first type of recursion is fine when the floor is 10. If it is 100, the program will run for a long time and no result will be produced for several minutes.
It is still recursive and cannot be passed even if it is submitted, but it is instructive for the second solution.
Recursive equation:
DropEggs(m,n) = min(1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x))，x=1,...n)
Recursive exit:
When m is 0 or n is 0, 0 is returned,
When m is 1, return n,
Returns 1 when n is 1.
explain:
Suppose an egg is thrown from floor x. If it is broken, the lowest broken egg floor is lower than x, then there are m-1 eggs left at this time.
You only need to explore the x-1 floor. If it is not broken and the lowest broken egg floor is above the x floor, then there are m eggs left at this time.
Just explore a total of n-x layers above x layer,
Since both are possible, and the question asks about the worst-case scenario, then take the scenario where the number of eggs needs to be thrown more times between the two scenarios,
That is, max(DropEggs(m-1,x-1),DropEggs(m, n-x))
Then, if you start throwing from layer x, you need to throw 1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x)) times in total.
1 means throwing the xth layer once. We need to know the optimal x, which is the minimum number of times the question needs to be asked,
Then you need to try all the possibilities of x, and finally get the answer. All the possibilities of x are 1,...,n.
When there are no eggs or floors, the number is 0.
When there is only one egg, you can only try it from the first floor up, or at worst, try all floors.
When there is only one layer, only try it once.
time complexity:
Index level
Note: The dynamic programming version itself is modified by recursion
Reference answers
The recursive version of this answer will fail if the parameters are large, but the answer is correct and can be used for local testing;
If readers use my code, be sure to add static identifiers to methods. Or write all the static methods of my answer as non-static methods, anyway, they need to be unified
public class Solution {<!-- -->
/**
* @param m: the number of eggs
* @param n: the number of floors
* @return: the number of drops in the worst case
*/
public static int dropEggs2(int m, int n) {<!-- -->
//return (int)f1(m,n); //Recursion, timed out
return dp(m,n); //Dynamic programming
}
public static int dp(int m,int n){<!-- -->
int[][] dp = new int[m + 1][n + 1];
//Fill the first column
for (int i = 1; i <=m ; i + + ) {<!-- -->
dp[i][0]=0;
dp[i][1]=1;
}
for (int j = 1; j <=n ; j + + ) {<!-- --> //Fill the second line
dp[1][j] =j;
}
for (int i = 2; i <=m ; i + + ) {<!-- -->
for (int j = 2; j <=n ; j + + ) {<!-- -->
dp[i][j] =Integer.MAX_VALUE;
for (int k = 1; k <j ; k + + ) {<!-- -->
int tmp = 1 + Math.max(dp[i-1][k-1],dp[i][j-k]);
dp[i][j]=Math.min(dp[i][j],tmp);
}
}
}
return dp[m][n];
}
//recursion
public static long f1(int m,int n){<!-- -->
/*
There are two methods, which are essentially the same. The first is recursive, which will time out but can produce results, and the second is dynamic programming.
The first type of recursion is fine when the floor is 10. If it is 100, the program will run for a long time and no result will be produced for several minutes.
It is still recursive and cannot be passed even if it is submitted, but it is instructive for the second solution.
Recursive equation:
DropEggs(m,n) = min(1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x))，x=1,...n)
Recursive exit:
When m is 0 or n is 0, 0 is returned,
When m is 1, return n,
Returns 1 when n is 1.
explain:
Suppose an egg is thrown from floor x. If it is broken, the lowest broken egg floor is lower than x, then there are m-1 eggs left at this time.
You only need to explore the x-1 floor. If it is not broken and the lowest broken egg floor is above the x floor, then there are m eggs left at this time.
Just explore a total of n-x layers above x layer,
Since both are possible, and the question asks about the worst-case scenario, then take the scenario where the number of eggs needs to be thrown more times between the two scenarios,
That is, max(DropEggs(m-1,x-1),DropEggs(m, n-x))
Then, if you start throwing from layer x, you need to throw 1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x)) times in total.
1 means throwing the xth layer once. We need to know the optimal x, which is the minimum number of times the question needs to be asked,
Then you need to try all the possibilities of x, and finally get the answer. All the possibilities of x are 1,...,n.
When there are no eggs or floors, the number is 0.
When there is only one egg, you can only try it from the first floor up, or at worst, try all floors.
When there is only one layer, only try it once.
time complexity:
Index level
*/
if(m ==0 || n==0) return 0;
if(m ==1) return n;
if(n==1) return 1;
long ans = Long.MAX_VALUE;
for (int i = 2; i <n + 1; i + + ) {<!-- -->
long tmp = 1 + Math.max(dropEggs2(m-1,i-1),dropEggs2(m,n-i));
if(ans > tmp)
ans = tmp;
}
return ans;
}
}
Code for local testing
public class LC584 {<!-- -->
public static int dropEggs2(int m, int n) {<!-- -->
//return (int)f1(m,n); //Recursion, timed out
return dp(m,n); //Dynamic programming
}
public static int dp(int m,int n){<!-- -->
int[][] dp = new int[m + 1][n + 1];
//Fill the first column
for (int i = 1; i <=m ; i + + ) {<!-- -->
dp[i][0]=0;
dp[i][1]=1;
}
for (int j = 1; j <=n ; j + + ) {<!-- --> //Fill the second row
dp[1][j] =j;
}
for (int i = 2; i <=m ; i + + ) {<!-- -->
for (int j = 2; j <=n ; j + + ) {<!-- -->
dp[i][j] =Integer.MAX_VALUE;
for (int k = 1; k <j ; k + + ) {<!-- -->
int tmp = 1 + Math.max(dp[i-1][k-1],dp[i][j-k]);
dp[i][j]=Math.min(dp[i][j],tmp);
}
}
}
return dp[m][n];
}
//recursion
public static long f1(int m,int n){<!-- -->
/*
There are two methods, which are essentially the same. The first is recursive, which will time out but can produce results, and the second is dynamic programming.
The first type of recursion is fine when the floor is 10. If it is 100, the program will run for a long time and no result will be produced for several minutes.
It is still recursive and cannot be passed even if it is submitted, but it is instructive for the second solution.
Recursive equation:
DropEggs(m,n) = min(1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x))，x=1,...n)
Recursive exit:
When m is 0 or n is 0, 0 is returned,
When m is 1, return n,
Returns 1 when n is 1.
explain:
Suppose an egg is thrown from floor x. If it is broken, the lowest broken egg floor is lower than x, then there are m-1 eggs left at this time.
You only need to explore the x-1 floor. If it is not broken and the lowest broken egg floor is above the x floor, then there are m eggs left at this time.
Just explore a total of n-x layers above x layer,
Since both are possible, and the question asks about the worst-case scenario, then take the scenario where the number of eggs needs to be thrown more times between the two scenarios,
That is, max(DropEggs(m-1,x-1),DropEggs(m, n-x))
Then, if you start throwing from layer x, you need to throw 1 + max(DropEggs(m-1,x-1),DropEggs(m, n-x)) times in total.
1 means throwing the xth layer once. We need to know the optimal x, which is the minimum number of times the question needs to be asked,
Then you need to try all the possibilities of x, and finally get the answer. All the possibilities of x are 1,...,n.
When there are no eggs or floors, the number is 0.
When there is only one egg, you can only try it from the first floor up, or at worst, try all floors.
When there is only one layer, only try it once.
time complexity:
Index level
*/
if(m ==0 || n==0) return 0;
if(m ==1) return n;
if(n==1) return 1;
long ans = Long.MAX_VALUE;
for (int i = 2; i <n + 1; i + + ) {<!-- -->
long tmp = 1 + Math.max(dropEggs2(m-1,i-1),dropEggs2(m,n-i));
if(ans > tmp)
ans = tmp;
}
return ans;
}
public static void main(String[] args) {<!-- -->
System.out.println(dropEggs2(2,36)); //8
System.out.println(dropEggs2(2,100)); //14
}
}