Force buckle 1884 Egg drop - two eggs

Buckle address

1884. Eggs fall - Two eggs

Medium difficulty 28

Here you are. 2 The same Of eggs , And a building from the 1 Layer to tier n There are layers in total n A building on the ground floor .

There are known floors f , Satisfy 0 <= f <= n , Any from higher than f All the eggs falling from the floor of It will break , from f Floor or lower All the eggs falling from the floor of It won't break .

Every operation , You can take one Not broken And take it from any floor x Throw down （ Satisfy 1 <= x <= n）. If the egg breaks , You can't use it again . If an egg is not broken after being dropped , Then you can in subsequent operations Reuse This egg .

Please calculate and return to confirm f The exact value Of Minimum number of operations How much is the ？

Example 1：

 Input ：n = 2
 Output ：2
 explain ： We can take the first egg from  1  Throw the building down , And then take the second one from  2  Throw the building down .
 If the first egg breaks , You know  f = 0;
 If the second egg breaks , But the first one didn't break , You know  f = 1;
 otherwise , When neither egg is broken , You know  f = 2.

Example 2：

 Input ：n = 100
 Output ：14
 explain ：
 An optimal strategy is ：
-  Remove the first egg from the  9  Throw the building down . If it breaks , that  f  stay  0  and  8  Between . Remove the second one from  1  Throw the building down , Then every time you throw it, go up to the next floor , stay  8  Found within times  f . Total number of operations  = 1 + 8 = 9 .
-  If the first egg doesn't break , Then take the first egg from  22  Layer drop . If it breaks , that  f  stay  9  and  21  Between . Remove the second egg from  10  Throw the building down , Then every time you throw it, go up to the next floor , stay  12  Found within times  f . Total number of operations  = 2 + 12 = 14 .
-  If the first egg doesn't break again , Then follow a similar method from  34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99  and  100  The first egg was dropped from the floor .
 Whatever the outcome , At most  14  Time to determine  f .

analysis ：

1. dp Definition

   dp(n, k) Now there are n The first floor needs to be verified , Now you have k An egg , Returns the minimum number of operations at this time .

2. base case

   • If there is no floor to verify (n == 0), No matter how many eggs you have, you don't have to operate .

   • If you have only one egg in your hand (k == 1), Then you can only start from 1 The building began to test ：1 floor 、2 floor 、…、n floor , A common need n operations .

   if(n == 0){
               return 0;
           }
   if(k == 1){
               return n;
           }
   
   

3. State shift

Now I have k An egg , Next, choose one layer and throw eggs , Suppose you choose No i layer ,

There are two situations ：

​ 1： It's broken , To be determined f stay [0,i-1] Inside , The floor to be verified is not i-1, Besides, I lost an egg , only k-1 An egg , The floor interval to be searched should be from [1..N] Turn into [1..i-1] common i-1 floor ;, The next step is to verify dp[i-1,k-1], Operating frequency +1;

​ 2： Not broken ： To be determined f stay [i,n] Inside , The number of floors to be verified next is n-i, And no eggs were lost , The floor interval to be searched should be from [1..N] Turn into [i+1..N] common N-i floor . The next step is to verify dp[n-i,k], Operating frequency +1;

The title requires ： At least a few operations are required in the worst case , At worst, between these two situations , Select the one that requires the most operations , Plus the operation of throwing eggs by yourself , namely Math.max(dp[i-1,k-1],dp[n-i,k])+1, This value is what you choose from the i Throw eggs on the first floor , The number of operations required in the worst case

4. dp[n,k] That is, the number of operations required ,

   It means that you choose the floor with the least number of operations in the worst case to throw eggs . So you need to traverse all floors , find Math.min(res, Math.max(dp(i-1, k-1), dp(n-i, k)) + 1).

5. Add a memo to eliminate overlapping sub problems

Code ：

class Solution {
    int[][] memo;
    public int twoEggDrop(int n) {
        memo=new int[n+1][3];
        return dp(n,2);
    }
    public int dp(int n,int k){
        //1. basecase
        if(n==0) return 0;
        if(k==1) return n;
        //2.  Look up the table 
        if(memo[n][k]!=0) return memo[n][k];
        //3. State shift 
        int res=Integer.MAX_VALUE;
        for(int i=1;i<=n;i++){
            res=Math.min(res,Math.max(dp(i-1,k-1),dp(n-i,k))+1);
            
        }
        memo[n][k]=res;
        return res;
    }
}