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蛋。 您必須盡量減少丟雞蛋的次數，以找到關鍵的地板，其中關鍵的地板意味著雞蛋開始破損的地板 。 問題的假設：
If egg breaks at ith floor then it also breaks at all greater floors.
如果雞蛋在第1層破裂，那么它在所有較大的層也破裂。
If egg does not break at ith floor then it does not break at all lower floors.
如果雞蛋沒有在我破樓那么它不會在所有低層打破。
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.降在一樓：
Egg does not break:
雞蛋不碎：
If egg does not break then we have three floors left and two eggs. We can either choose
如果雞蛋沒有破裂，那么我們剩下三層樓和兩個雞蛋。 我們可以選擇
2nd or 3rd floor and proceed similarly but we can easily see we have to do atleast 3 trials.
2 次或3 樓 ，同樣繼續進行，但我們可以很容易地看到，我們所要做的ATLEAST 3項試驗。
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。掉到二樓：
Egg breaks:
雞蛋休息時間：
We are left with one egg and we have to check only 1 floor so number of trials 2.
我們只剩下一個雞蛋，我們只需要檢查1層，那么試驗次數為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 3rd and 4th floor is same as dropping from 2nd and 1st floor respectively only difference is that subcases A and B just gets swapped.
注意：從跌落3 和 第 4層是與從第 2和第 1層分別唯一的區別滴是子情況A和B只是獲取交換。
Algorithm:
算法：
Create a 2D dp matrix where jth cell of ith row represents the minimum number of trials needed to check i floors using j eggs.
創建一個二維dp矩陣，其中第 i行的第j 個單元格代表使用j個雞蛋檢查i個樓層所需的最小試驗次數。
If there are 0 eggs then there are 0 trials so initializing all cell corresponding to this situation.
如果有0個卵，則有0個試驗，因此初始化對應于這種情況的所有單元。
If there are 1 egg then we have to drop egg at every floor so the number of trials is number of floors.
如果有1個雞蛋，那么我們必須在每個樓層放雞蛋，這樣試驗的次數就是樓層數。
If there are 0 floors so there are 0 trials and if there is one floor there is only one trial.
如果樓層數為0，則試驗為0，而樓層數為1，則只有一次試驗。
Start filling the dp matrix from egg = 2 && floors = 2.
從egg = 2 && floors = 2開始填充dp矩陣。
We have to choose a floor x between the 1 – floor and then find cases when egg breaks at xth floor and egg do not break at xth floors (A and B subparts of cases).
我們有選擇的1樓之間的地板X -地板，然后找到情況下，當在X 樓和雞蛋的蛋破裂不會在第 X層(例A和B子部分)打破。
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 xth floor.
由于我們正在考慮最壞的情況，因此我們必須充分利用這些A和B子部分。 此外，我們還將添加一個到它也需要一個試驗檢查X 樓 。
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 <iostream>
#include <limits.h>
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 program
int 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
輸出量
4
2
number of trials when number of eggs is 2 and number of floors is 4: 3
翻譯自: https://www.includehelp.com/algorithms/egg-dropping-problem-using-dynamic-programming.aspx
dp 扔雞蛋
