This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

The problem of losing pieces

Problem description

A building has n+1 floors, with the ground floor counted as floor 0 and the highest floor as floor N. We know that a piece falling from tier 0 will not break, and a piece falling from tier I may or may not break. Given an integer n as the number of floors and an integer k as the number of pieces, returns the minimum number of throws if you want to find the number of topmost pieces that will not break, even in the worst case. You can only throw one piece at a time.

The sample

Input: 10, 1

Output: 10

Explanation: Because there is only one chess piece, we have to try from the first layer to the 10th layer. In the worst case, the 10th layer is the highest layer that will not be broken, so we have to throw at least 10 times

To analyze problems

So, first of all, let’s say f(n,k) is the minimum number of experiments that we can do with n floors,k pieces, in the worst case.

Let’s consider a piece dropped from the JTH layer, and it can go into two states: broken and unbroken.

  1. If it is broken, it means that the number of layers above the j layer must still be broken, so the number of layers greater than J can be ignored. At this time, only K-1 chess pieces and J-1 floors are left, and the remaining number of experiments is F (J-1, K-1).
  2. Not broken, indicating that the number of layers j and below must not be broken when they are dropped, so the number of layers less than j can be ignored. At this time, there are still K pieces (because this piece is not broken, it can still be used) and n-J floors, and the remaining number of experiments is F (n-j, k).

There are some special cases to consider here.

  • If n=0, you’re on the ground, you’re not going to break, so you don’t have to do any experiments, so f=0
  • If k=1, it means that there is only one chess piece, we have to operate layer by layer, the worst case, that is, the NTH floor will be broken, in this case, n experiments are needed, so f=n.

Because we don’t know from the first j layer dropped pieces will be dashed to pieces, and the requirements of the subject is the worst case, namely the maximum of the above two cases, and the value of j is uncertain, it is value in the range of [1, n), therefore, we need to enumerate all the j, calculation of j all values corresponding to the minimum number of that one, to say the least number of experiment.

We can do this recursively, so let’s look at the code.

Import sys class Solution(object): def solve(self,n,k): Return n res=sys.maxsize #j for j in range(1,n+1): Solve (j-1, k-1), self.solve(n-j, k))) return res = min(res, 1 + Max (self.solve(j-1, k-1), self.solve(n-j, k)Copy the code

The time complexity of this algorithm is O(n!). , the space complexity is O(1). The time complexity of this algorithm is too high, so let’s see how to optimize it.

To optimize the

This is a problem we can solve using dynamic programming. According to the relationship deduced above, it can be known that the transfer equation of dynamic programming is:

Dp [I] [j] = min (1 + Max (dp [p – 1] [1], dp [I – p] [j])), including the range of p is [1, k]

Dp [I][j] represents I floor, J pieces, and the minimum number of experiments in the worst case.

Let’s take a look at the code implementation.

import sys class Solution(object): def solve(self,n,k): if n==0: return 0 if k==1: Print print print print print print print print print print print print print print print dp[i][1]=i for i in range(1, n+1): for j in range(2,k+1): dp[i][j]=sys.maxsize for p in range(1,i+1): # transfer equation of the dp [I] [j] = min (dp [j], [I] 1 + Max (dp [p - 1] [1], dp [I - p] [j])) return dp [n] [k]Copy the code

The time complexity of this algorithm is O(n^2 * k) and the space complexity is O(NK).

The ultimate solution to

Here we use reverse thinking to solve, the problem is to find n floors, k pieces in the worst case need to throw the minimum number of times. Now we reverse the problem, see I pieces thrown j times, can measure the maximum number of floors of the problem (meaning that every time still the position is the optimal and in the case of the chess pieces are sure enough), here is expressed by dp[I] [j].

Now let’s consider that the ith piece is dropped on the optimal floor, and two things can happen.

  • It is broken, so the upper layer does not need to be measured, the lower layer can be measured dp[I-1] [J-1] layer.
  • Not broken, then the following does not need to measure, above can measure dp[I] [J-1] layer.
  • So can the layer where the ith piece is dropped.

To sum up, considering the worst case (i.e., the number of floors that can be measured at most when I pieces are thrown j times), the state transfer equation can be obtained as follows:

​ dp[i] [j] = dp[i-1] [j-1] + dp[i] [j-1] + 1

  1. Initial: Dp [I] [1] =1 because no matter how many pieces there are, only one floor can be measured at a throw.

  2. Final answer: I does not exceed k, such that dp[I] [j] >= n minimum j.

Now we can have two more optimizations.

  • We know that N floors can be directly determined by throwing log2N+1 times in a binary manner, so when the given number of pieces is greater than logN+1, we simply return log2N+1.

  • As the state transition equation is dp[I] [j] = DP [i-1] [J-1] + DP [I] [J] + 1, that is, dp[I] [j] only and its upper left element DP [i-1] [J-1] and its left element DP [I] [J-1], So we can compress to one dimension and need to calculate from right to left, as shown below:

As shown in the figure, we use pink to represent DP [I] [j] and yellow to represent DP [I] [J-1]. When calculating DP [j], we traverse from right to left. At the beginning, dp[j] is yellow, and the result of last iteration dp[I] [J-1] is stored. J-1 is also yellow. So dp [j] = dp [j] + dp] [j – 1 + 1 is equivalent to the dp [I] [j] = dp [I] [1] + dp [I – 1]] [j – 1 + 1.

Let’s look at the implementation of the code.

import sys import math class Solution(object): def solve(self,n,k): if n==0: return 0 if k==1: B = int(math.log2(n) +1) if k >= b: return b dp = [1] * (k+1) res=1 while True: res=res+1 for j in range(k,1,-1): print(j) dp[j] = dp[j] + dp[j-1] + 1 if dp[j] >=n: return res dp[1]=resCopy the code

The time complexity of this algorithm is O(klogN), because the outer loop while iterates at most logn rounds, otherwise it can be solved directly by binary throwing chess pieces. The energy layer cycle is K times, so the total time complexity is O(klogN), and the space complexity is O(n).