dp 扔鸡蛋

Problem statement: You are given N floor and K eggs. You have to minimize the number of times you have to drop the eggs to find the critical floor where critical floor means the floor beyond which eggs start to break. Assumptions of the problem:

问题陈述：给您N楼和K蛋。 您必须尽量减少丢鸡蛋的次数，以找到关键的地板，其中关键的地板意味着鸡蛋开始破损的地板 。 问题的假设：

1. If egg breaks at i^th floor then it also breaks at all greater floors.

   如果鸡蛋在^第1层破裂，那么它在所有较大的层也破裂。

2. If egg does not break at i^th floor then it does not break at all lower floors.

   如果鸡蛋没有在我破^楼那么它不会在所有低层打破。

3. Unbroken egg can be used again.

   完整的鸡蛋可以再次使用。

Note: You have to find minimum trials required to find the critical floor not the critical floor.

注意：您必须找到找到关键楼层而不是关键楼层所需的最少试验。

Constraints:

限制条件：

1 <= N <= 1000    1 <= K <= 100

Example 1:

范例1：

Input:    4    2        Output:    Number of trials when number of eggs is 2 and number of floors is 4: 3

Example 2:

范例2：

Input:    36    2    Output:    Number of trials when number of eggs is 2 and number of floors is 36: 8

Explanation of the problem:

问题说明：

For the Input 1,

对于输入1，

Case 1. Drop at first floor:

案例1.降在一楼：

1. Egg does not break:

   鸡蛋不碎：

   If egg does not break then we have three floors left and two eggs. We can either choose

   如果鸡蛋没有破裂，那么我们剩下三层楼和两个鸡蛋。 我们可以选择

   2^nd or 3^rd floor and proceed similarly but we can easily see we have to do atleast 3 trials.

   2 ^次或3 ^楼 ，同样继续进行，但我们可以很容易地看到，我们所要做的ATLEAST 3项试验。

2. Egg breaks:

   鸡蛋休息时间：

   If egg breaks then we found the critical floor in only 1 trial.

   如果鸡蛋破裂，那么我们仅在1次试验中发现了临界水平。

In case 1, the worst possibility is that egg does not break so trials will be 3 for case 1.

在第一种情况下，最可能的情况是鸡蛋不会破裂，因此第一种情况下的试验为3。

Case 2. Drop at second floor:

情况2。掉到二楼：

1. Egg breaks:

   鸡蛋休息时间：

   We are left with one egg and we have to check only 1 floor so number of trials 2.

   我们只剩下一个鸡蛋，我们只需要检查1层，那么试验次数为2。

2. Egg does not break:

   鸡蛋不碎：

   We still have two eggs and two floors to check we have to check one by one on these floors so trials needed are 3.

   我们仍然有两个鸡蛋和两个楼层要检查，我们必须在这些楼层上一个接一个地检查，因此需要进行3次试验。

So for case 2 together the worst possibility is 3.

因此，对于情况2，最坏的可能性是3。

In the end we have to find the minimum of case 1, case 2, case 3, case 4.

最后，我们必须找到情况1，情况2，情况3，情况4的最小值。

Note: Dropping from 3^rd and 4^th floor is same as dropping from 2^nd and 1^st floor respectively only difference is that subcases A and B just gets swapped.

注意：从跌落3 ^{和 第} 4层是与从^第 2和^{第 1}层分别唯一的区别滴是子情况A和B只是获取交换。

Algorithm:

算法：

1. Create a 2D dp matrix where j^th cell of ith row represents the minimum number of trials needed to check i floors using j eggs.

   创建一个二维dp矩阵，其中^第 i行的第j ^个单元格代表使用j个鸡蛋检查i个楼层所需的最小试验次数。

2. If there are 0 eggs then there are 0 trials so initializing all cell corresponding to this situation.

   如果有0个卵，则有0个试验，因此初始化对应于这种情况的所有单元。

3. If there are 1 egg then we have to drop egg at every floor so the number of trials is number of floors.

   如果有1个鸡蛋，那么我们必须在每个楼层放鸡蛋，这样试验的次数就是楼层数。

4. If there are 0 floors so there are 0 trials and if there is one floor there is only one trial.

   如果楼层数为0，则试验为0，而楼层数为1，则只有一次试验。

5. Start filling the dp matrix from egg = 2 && floors = 2.

   从egg = 2 && floors = 2开始填充dp矩阵。

6. We have to choose a floor x between the 1 – floor and then find cases when egg breaks at x^th floor and egg do not break at x^th floors (A and B subparts of cases).

   我们有选择的1楼之间的地板X -地板，然后找到情况下，当在X ^楼和鸡蛋的蛋破裂不会在^第 X层(例A和B子部分)打破。

7. We have to take the maximum of these A and B subparts as we are taking worst case possible. Also, we will also add one to it as one trial is also needed to check x^th floor.

   由于我们正在考虑最坏的情况，因此我们必须充分利用这些A和B子部分。 此外，我们还将添加一个到它也需要一个试验检查X ^楼 。

8. Taking the minimum of answers of all such x's and storing at my particular number of floors and number of eggs.

   以所有这些x的最小答案，并以我的特定楼层数和鸡蛋数存储。

The time complexity of the above code is O(N * K * K).

上面代码的时间复杂度为O(N * K * K)。

使用动态编程(DP)解决鸡蛋掉落问题的C ++程序 (C++ program for Egg dropping problem using Dynamic Programming (DP))

#include 
    
     #include 
     
      using namespace std;int eggDrop(int floors, int eggs){
   	int dp[floors + 1][eggs + 1] = {
   0};	// intializing with some cases	// case 1. when there are 0 floors	for(int egg = 0;egg<=eggs;egg++){
   		dp[0][egg] = 0;	}	// case 2. when there are only 1 floor so there 	// are only 1 way only check the first floor	for(int egg = 0;egg<=eggs;egg++){
   		dp[1][egg] = 1;	}	// case 3. when there are 0 eggs	for(int floor = 0;floor <=floors;floor++){
   		dp[floor][0] = 0;	}	// case 4. when there are 1 egg then we have to 	// check every floor so our answer would be number of 	// floors	for(int floor = 0;floor <= floors;floor++){
   		dp[floor][1] = floor;	}	// we will start filling dp matrix from 	// floor = 2 && egg = 2	for(int egg = 2;egg<=eggs;egg++){
   		for(int floor = 2;floor<=floors;floor++){
   			// choosing an ith floor between 1 - floor			int mini = INT_MAX;			for(int i = 1;i<=floor;i++){
   				// dp[i - 1][egg-1] means to find the answer when 				// the egg is broken at ith floor				// dp[floor - i][egg] means to find the answer 				// when the egg is not broken at ith floor				int ans = max(dp[i-1][egg-1], dp[floor - i][egg]);				// by trying to check the floor i have used one trial				ans++;				// taking the minimum of all possible floor 				// possible between 1 - floor				mini = min(mini, ans); 			}			// storing the answer			dp[floor][egg] = mini;		}	}	return dp[floors][eggs];}// driver programint main() {
   	int floors, eggs;	cin >> floors >> eggs;	cout<<"number of trials when number of eggs is " << eggs;	cout<<" and number of floors is " << floors;	cout<<": "  << eggDrop(floors,eggs);	return 0;}
     
    

Output

输出量

42number of trials when number of eggs is 2 and number of floors is 4: 3

翻译自:

dp 扔鸡蛋