在本教程中，我们将解决另一个经典的DP问题。
这个问题很难理解。因此，首先我们将在递归的帮助下解决这个问题。稍后我们将看到如何使用DP解决它。
问题陈述：
给您“ n”层和“ m”个鸡蛋。您需要找出鸡蛋从哪一层破损的次数最少。
假设：
- 如果鸡蛋从“ n”层破损，则鸡蛋将从其上方的所有层破损。
- 如果鸡蛋不会从n楼摔破，那么如果鸡蛋从“ n”的较低楼层摔下来，也不会摔破。
我们将通过以下几点来理解上述问题。
例如，您有6层地板和1个鸡蛋。
你不能直接去6日 地板，扔鸡蛋，检查它是否破裂。因为，如果鸡蛋破裂，您将无法知道鸡蛋是否在5楼破裂。
因此，我们从1楼开始，然后扔鸡蛋。如果破损，我们将标记为从一楼开始破蛋。
如果鸡蛋没有破裂，那么我们将把鸡蛋从2nd 楼，如果鸡蛋没有破裂，我们转到3rd 直到我们达到6日 地板。
因此，在最坏的情况下，我们需要将鸡蛋丢“ n”次。
假设您有10层地板和2个鸡蛋。那你就可以把5个鸡蛋丢了日 地板。如果鸡蛋破裂，则鸡蛋数目为1，要检查的层数为4。因为我们已经知道鸡蛋将从5破裂日 地板。因此，根据我们的假设，鸡蛋也会从上面的地板上破裂。因此，我们需要检查它下面的地板。
如果鸡蛋没有从第5层破损，那么我们仍然有2个鸡蛋，我们还有4层要检查。为什么是4层？
因为10 -5 -1 = 4。
我们已经知道鸡蛋从5断裂日 地板，可以表示为
再次，如果我们从3扔鸡蛋rd 地板破损，如果破损，我们有1个鸡蛋，或者如果鸡蛋未破损，我们从2楼起检查有2个鸡蛋。
我们可以编写如下的递归公式：
egg_drop（n）
对于i = 1到no_of_floors
temp = 1 + max（egg_drop（egg-1，i-1），egg_drop（egg，floor-i））
最后，当程序从1到n遍历所有楼层时，temp的最小值将是答案。
在公式中，我们添加了1，因为从特定楼层投掷时我们已经进行了1次尝试。
我们使用egg_drop（egg-1，i-1）是因为我们假设鸡蛋破裂了，因此我们少了1个鸡蛋。
我们使用egg_drop（egg，floor-i），因为鸡蛋没有从该地板破损，需要检查上面的地板。
现在，我们将看到如何在DP的帮助下解决此问题。
假设我们有6层鸡蛋和2个鸡蛋，我们的DP阵列将如下所示：
在DP中，最好从0开始，因为这将有助于进一步解决问题。
- 在DP数组中，我们将填充最少的尝试次数。最后，我们获得尝试检查从哪个地板破蛋的最小次数。
- 最初，如果您有0个鸡蛋，那么整行将为0。
- 同样，如果我们有0层，则最小尝试次数也将为0。因此，我们将该列写为0。
可以如下更新：
现在您有1个鸡蛋和6层地板。所以你把鸡蛋从1ST 地板上，鸡蛋没有破裂。再一次你去2nd 地板放下，鸡蛋没有破裂。因此，您从3开始执行类似的操作rd , 4日 , 5日 , 6日 地板。因此，如果您有1个鸡蛋和n个楼层，则最小尝试次数将等于最低值。
因此我们可以如下更新DP阵列
现在我们有2个鸡蛋。
同样，我们有2个鸡蛋和1个地板。因此，最大尝试次数将为1。
同样，我们有2个鸡蛋和2个楼层。所以首先我们从二楼尝试，然后扔鸡蛋，然后尝试了1次尝试。
现在，如果鸡蛋破裂，我们将得到1个鸡蛋和1个地板。
否则，如果鸡蛋没有破裂，我们将拥有2个鸡蛋和1个地板。
因此，我们检查DP [1，1]和DP [2，1]的值。
记住我们的递归公式：
1 +最大[dp [1，1]，dp [2，1]]
即1 + max [1，1] = 2
现在集中精力：
现在我们有2个鸡蛋和3层楼。
为此，我们将有2个指针，如下图所示，并且最初我们获得max_value +1。因此，从以上获得的最大值中，我们取最小值并进行更新。
即首先我们比较
1+最大[0，1] = 2
1+最大[1，1] = 2
1+最大[0，2] = 3
现在我们在温度中有3个值，即[2，2，3]。我们应该取3个值中的最小值。即2
现在，当我们有2个鸡蛋和4个楼层时，我们将以类似的方式求解
现在，在临时数组中，我们有4个值[3、3、4、3]。最小值为3。
以类似的方式，我们计算出我们有5层2个鸡蛋和6层2个鸡蛋的位置。
最终的DP矩阵如下：
因此，当我们有6层地板和2个鸡蛋时，我们至少需要3次尝试。
C ++解决方案
#include <iostream>
using namespace STd;
// helper function to get max number
int max(int a, int b)
{
return (a > b) ? a : b;
}
int egg_drop_problem(int no_of_eggs, int no_of_floor)
{
// Base case: if no floor or 上ly 上e floor
// return.
if (no_of_floor == 1 || no_of_floor == 0)
return no_of_floor;
// We need no_of_floor trials for 上e egg and no_of_floor floors
if (no_of_eggs == 1)
return no_of_floor;
int min = INT_MAX, x, res;
for (x = 1; x <= no_of_floor; x++)
{
res = max(
egg_drop_problem(no_of_eggs - 1, x - 1),
egg_drop_problem(no_of_eggs, no_of_floor - x));
if (res < min)
min = res;
}
return min + 1;
}
int main()
{
int no_of_eggs = 2;
int no_of_floor = 6;
cout << "Minimum number of tries in worst case with "
<< no_of_eggs << " eggs and with " << no_of_floor
<< " floors is "
<< egg_drop_problem(no_of_eggs, no_of_floor) << endl;
return 0;
}
输出：
Minimum number of tries in worst case with 2 eggs and with 6 floors is 3
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
