[topic address]

You are given k of the same eggs and can use a building with n floors from the first to the NTH.

It is known that there exists a floor F such that 0 <= f <= n, and any egg dropped from a floor above f will break, and no egg dropped from floor F or a floor below it will break.

For each operation, you can take an unbroken egg and drop it from any floor X (1 <= x <= n). If the egg breaks, you can’t use it again. If an egg does not break after being dropped, it can be reused in subsequent operations.

Please calculate and return what is the minimum number of operations required to determine the exact value of f?

Example 1:

Input: k = 1, n = 2 Output: 2 Explanation: The egg fell from the first floor. If it breaks, I'm sure that f is equal to 0. Otherwise, the egg falls from the 2nd floor. If it breaks, I'm sure that f is equal to 1. If it doesn't break, then you definitely get f is equal to 2. So in the worst case we have to move it 2 times to figure out what f is.Copy the code

Example 2:

Input: k = 2, n = 6 Output: 3Copy the code

Example 3:

Input: k = 3, n = 14 Output: 4Copy the code

 

Tip:

  • 1 <= k <= 100
  • 1 <= n <= 104

The front information

So just to make it easier for you to understand how to throw eggs, let’s look at the fixed floor and the number of eggs, how do we solve for f?

It can be seen that when there is only one egg, in order to reliably find F, we can only try from the first layer up layer by layer, while when there are multiple eggs, we can split the interval, greatly improving the efficiency of searching.

First edition of dynamic programming

Their thinking

First of all, given dynamic conditions, the problem of optimal value can be solved by dynamic programming. In this case, we have two dynamic conditions, k eggs, n stories. Therefore, we can define a two-dimensional dp => dp[I][j], which represents the minimum number of operations required by I eggs and J floors. Now let’s think about how do we derive dp[I][j]? In fact, there are only two results of throwing eggs, eggs broken and eggs not broken. So let’s assume that the egg is thrown at the k (1<=k<=j) layer. If the egg breaks, then dp[I][j] = DP [i-1][K-1]+1, that is, the egg has i-1, and the floor to look for is k-1. If the egg is not broken, then dp[I][j] = dp[I][j-K]+1, that is, the egg has I, and the j-K layer is also to be found. Because we want to consider the worst case, so I can get the equation of state: dp [I] [j] = min (dp [I] [j], Max (dp [I – 1]] [k – 1, dp [I] [j] – k) + 1)

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; Dp = Array(K+1); for(let i = 0; i<=K; I ++){dp[I] = Array(N+1).fill(0)} i<=N; I++) {dp [1] [I] = I} / / using the state transition equation, deduces dp [K] [N] for (let I = 2; i<=K; i++){ for(let j = 1; j<=N; j++){ dp[i][j] = j; for(let k = 1; k<=j; K++) {dp [I] [j] = math.h min (dp [I] [j]. Math. Max (dp [I - 1], [k - 1] dp [I] [j] - k) + 1)}}} / / return the result return dp [k] [N]. };Copy the code

Such a version of the code though logic is no problem, the basis of test cases can also pass, but commit timeout, because we pray for all the process of two-dimensional dp, the double loop is used to collect all the eggs with the combination of the floor, and the number of floors of traversal for current dp value, so the time complexity is O (KN squared).

Binary optimization

Their thinking

Next, we thought about how to optimize the previous version of the code to improve the efficiency of deriving DP. Let’s look at the state transition equation again: Dp [I] [j] = min (dp [I] [j], Max (dp [I – 1], [k – 1] dp [I] [j] – k) + 1) we observed dp [I – 1] and [k – 1] dp [I] [j] – k, the former will be according to the k value increases, and decreases the latter will be according to the k value, Similarly, the former decreases as k decreases, while the latter increases as k decreases. And since we need to take the maximum of the two to update DP, so to get the optimal DP, we need to make k close to a middle value, make the two values as equal as possible, so that the maximum of them is as small as possible. Therefore, we can reduce the time complexity of the innermost layer search k value from O(N) to O(logN) through binary search of the target K value, and the overall time complexity is O(KNlogN).

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; Dp = Array(K+1); for(let i = 0; i<=K; I ++){dp[I] = Array(N+1).fill(0)} i<=N; I++) {dp [1] [I] = I} / / using the state transition equation, deduces dp [K] [N] for (let I = 2; i<=K; i++){ for(let j = 1; j<=N; j++){ dp[i][j] = j; // let l = 1,r = j; while(l<r){ const mid = (l+r)>>1; if(dp[i-1][mid-1]<dp[i][j-mid]) l = mid+1 else r = mid } dp[i][j] = Math. Min (dp [I] [j]. Math. Max (dp [I - 1], [l - 1] dp [I] [j] - l) + 1)}} / / return the result return dp [K] [N]. };Copy the code

This time the commit was ok, but the result was still not good, and the execution time was around 300ms.

K value of memory

Their thinking

Next we thought about how else we could optimize the code from the previous version. We consider such a problem, in our inner circle (1~N), j is monotonically increasing, then the optimal value of k must be monotonically increasing. So every time j increases, we just need to look for the optimal k value based on the last k value. This optimizes the time complexity to O(KN).

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; Dp = Array(K+1); for(let i = 0; i<=K; I ++){dp[I] = Array(N+1).fill(0)} i<=N; I++) {dp [1] [I] = I} / / using the state transition equation, deduces dp [K] [N] for (let I = 2; i<=K; I++){// let K = 1; for(let j = 1; j<=N; j++){ dp[i][j] = j; While (dp [I - 1]] [k - 1 < dp [I] [j] - k) k++ dp [I] [j] = math.h min (dp [I] [j]. Math. Max (dp [I - 1]] [k - 1, dp [I] [j] - k) + 1)}} / / return the result return dp[K][N]; };Copy the code

This version of code submission is significantly more efficient than before, and the execution time is about 150ms. But the overall results were still disappointing, beating only about 30 percent of users.

Memory K value + scroll array

Their thinking

Next we can optimize our code. We observe the state transition equation: Dp [I][j] = min(dp[I][j], Max (dp[i-1][k-1],dp[I][j-k])+1) dp[I] = min(dp[I][j], Max (dp[i-1][k-1], DP [I][j-k])+1) From O(KN) to O(N).

Scroll to the array

Let’s do a little bit of scrolling through an array. I %2 = 1; I %2 = 1; I %2 = 1; I %2 = 1; I %2 = 1;

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; Dp = Array(2); for(let i = 0; i<2; I ++){dp[I] = Array(N+1).fill(0)} i<=N; I++) {dp [1] [I] = I} / / using the state transition equation, deduces dp [K] [N] for (let I = 2; i<=K; I ++){// Let cur = I %2,pre =! cur*1; // let K = 1; for(let j = 1; j<=N; j++){ dp[cur][j] = j; While (dp [pre] [k - 1] < dp [cur] [j] - k) k++ dp (cur) [j] = math.h min (dp (cur) [j]. Math. Max (dp [pre] [k - 1), dp [cur] [j] - k) + 1)}} / / return the result  return dp[K%2][N]; };Copy the code

After the code was submitted, it beat 80+% of users in memory consumption.

Backward version of dynamic programming

Their thinking

For the above state definition, the fourth version of the code has basically done all the points that can be optimized, but still cannot reach the optimal solution. So let’s try another state definition here. Here, we define two-dimensional dp => dp[I][j], where I represents the number of operations, j represents the number of eggs, and DP [I][j] represents the highest floor that can be measured with J eggs. The derivation of the transfer equation is the same as before, but once again there are only two cases, the egg breaks and the egg doesn’t break. If the egg breaks, the floor that does not break can be measured as DP [I-1][J-1]. If it doesn’t break, then we can continue to use the egg, and at this point we can continue to look up the DP [i-1][j] layer. Then, combined with the current layer, so I can get the equation of state: dp [I] [j] = dp [I – 1]] [j – 1 + 1 + dp [I – 1] [j].

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; Dp = [Array(K+1).fill(0)]; // let num = 0; // if dp[num][K] is less than the target floor, While (dp[num][K]<N){num++ // initialize dp[num] dp[num] = [0] // derive dp for(let j = 1; j<=K; J++) {dp (num) [j] = dp [num 1]] [j - 1 + 1 + dp (num 1) [j]}} / / return operation times return num; };Copy the code

Num indicates the final number of operations. In this case, the time complexity is O(numK) and the space complexity is O(numK). Because the relationship between num and N is exponential, the time complexity of the solution is O(KlogN), and the space complexity is O(KlogN). Both the post-commit execution time and memory consumption beat 80+% of users, which is pretty close to the optimal solution.

One-dimensional DP optimization

Their thinking

In the process of deducing DP, the value of this time only depends on the number of last operation, so the DP array can be optimized to one-dimensional DP. Dp [I] represents the highest floor that can be measured by I eggs under the current number. Since the next time depends on the previous value, it should be pushed backwards. So update dp layer by layer.

Code implementation

Let superEggDrop = (K, N)=> {if(K===1) return N; // / initialize dp Array const dp = Array(K+1).fill(0); // let num = 0; While (dp[K]<N){// while(dp[K]<N){// while(dp[K]<N){ // derive dp for(let I = K; i>0; I -) {dp [I] = dp] [I - 1 + 1 + dp [I]}} / / return operation times return num; };Copy the code

The time complexity of this solution is the same as that of the previous version, O(KlogN), and the space complexity is O(K). Both the post-commit execution time and memory consumption beat 90+% users to reach the optimal solution.

At this point we are done with Leetcode-887 – egg drop

If you have any questions or suggestions, please leave a comment!