887. egg drop

Buckle address

Dynamic programming + Two points search

​ First of all, according to dp(K, N) Definition of array （ Yes K An egg to face N floor , At least throw dp(K, N) Time ）, It's easy to know K When fixed , This function follows N It must be monotonically increasing , No matter how smart you are , If the floor is increased , The number of tests must be increased .

​ Be careful dp(K - 1, i - 1) and dp(K, N - i) These two functions , among i It's from 1 To N It's just that , If we fix it K and N, Think of these two functions as about i Function of , The former follows i The increase of the should also be monotonous , The latter follows i The increase should be monotonous ：

Find the greater of the two , And then find the minimum of these maxima , In fact, it is to find the intersection of these two straight lines , That's the lowest point of the red broken line . It can be used at this time Two point search To find the lowest point

Looking back at these two dp Curve of function , The lowest point we're looking for is actually this situation ：

for (int i = 1; i <= N; i++) {
    if (dp(K - 1, i - 1) == dp(K, N - i))
        return dp(K, N - i);
}

namely ：

lo, hi = 1, N
        while lo <= hi:
            mid = (lo + hi) // 2
            broken = dp(K - 1, mid - 1) #  broken 
            not_broken = dp(K, N - mid) #  Not broken 
            # res = min(max( broken , Not broken ) + 1)
            if broken > not_broken:
                hi = mid - 1
                res = min(res, broken + 1)
            else:
                lo = mid + 1
                res = min(res, not_broken + 1)

        memo[(K, N)] = res
        return res

If you use dp Array to represent the above dp The definition of a function is ：

dp[k][n] = m
#  The current state is  k  An egg , face  n  floor 
#  The minimum number of eggs thrown in this state is  m

Determine the current number of eggs and the number of floors facing , You know the minimum number of eggs to throw . In the end, the answer we want is dp(K, N) Result .

1. Redefinition dp Definition of array , Determine the current number of eggs and the maximum number of egg throwing allowed , You know you can be sure F The highest number of floors .

dp[k][m] = n
#  The current is  k  An egg , You can try to throw  m  The second egg 
#  In this state , In the worst case, at most one building can be tested  n  A three story building 

#  for instance  dp[1][7] = 7  Express ：
#  Now there is  1  An egg , You are allowed to throw  7  Time ;
#  In this state, I can give you at most  7  floor ,
#  So you can determine the floor  F  So that the eggs just don't break 
# （ Layer by layer linear exploration ）

here m Is an upper bound of the degree , Here we are going to do this by dp[k][m] Number of approaching floors , To find this m,

The title is not Here you are. K egg ,N floor , Let's ask for the least number of tests in the worst case m Do you ？while The condition for the end of the cycle is dp[K][m] == N, That is to say Here you are. K An egg , Allow testing m Time , In the worst case, you can test at most N floor .

2. State shift

1、 No matter what floor you're on, throw eggs , Eggs can only be broken or not broken , If it's broken, measure it downstairs , If it's not broken, it will be measured upstairs .

2、 Whether you go upstairs or downstairs , The total number of floors = The number of floors upstairs + The number of floors downstairs + 1（ The current floor ）.

According to this feature , You can write the following state transition equation ：

dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1

dp[k][m - 1] It's the number of floors upstairs , Because count the eggs k unchanged , That is, the eggs are not broken , The number of eggs thrown m Minus one ;

dp[k - 1][m - 1] It's the number of floors downstairs , Because count the eggs k Minus one , That is, the eggs are broken , Number of eggs thrown at the same time m Minus one .

PS： This m Why subtract one, not add one ？ It was clearly defined before , This m Is an upper bound of the number of times allowed , Instead of throwing it a few times .

namely ：

int superEggDrop(int K, int N) {
    // m  Not more than  N  Time （ Linear scanning ）
    int[][] dp = new int[K + 1][N + 1];
    // base case:
    // dp[0][..] = 0
    // dp[..][0] = 0
    // Java  The default initialization array is  0
    int m = 0;
    while (dp[K][m] < N) {
        m++;
        for (int k = 1; k <= K; k++)
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
    }
    return m;
}

Code

class Solution {
    
    public int superEggDrop(int k, int n) {
    
        int[][] dp=new int[k+1][n+1];
        int m=0;
        while(dp[k][m]<n){
    
            m++;
            for(int i=1;i<=k;i++){
    
                // Floor number = The upper + The lower + This layer 
                dp[i][m]=dp[i][m-1]+dp[i-1][m-1]+1;
            }
        }
        return m;
    }
}