下面是这个著名谜题的实例描述，涉及n=2个鸡蛋和一栋k=36层的建筑。 假设我们想知道36层建筑中的哪些楼层可以安全地投鸡蛋，哪些楼层会导致鸡蛋在着陆时破裂。我们做了一些假设： …..一枚能在坠落中存活下来的蛋可以再次使用。 …..破鸡蛋必须扔掉。 …..跌落对所有鸡蛋的影响都是一样的。 …..如果鸡蛋掉下来会碎，那么它从更高的地板上掉下来就会碎。 …..如果一只蛋能在一次坠落中存活下来，那么它能在一次较短的坠落中存活下来。 …..不排除一楼的窗户会打碎鸡蛋，也不排除36楼不会导致鸡蛋破裂。 如果只有一个鸡蛋可用，并且我们希望确保获得正确的结果，那么实验只能以一种方式进行。把鸡蛋从一楼的窗户扔下来；如果它还活着，就把它从二楼的窗户扔下来。继续向上直到它断裂。在最坏的情况下，这种方法可能需要36次排泄。假设有两个鸡蛋。保证在所有情况下都有效的最少卵子排泄量是多少？ 问题其实不是找到临界楼层，而是仅仅决定从哪个楼层投下卵子，从而使试验总数最小化。 资料来源： 动态规划维基
null
方法1 : 递归。 在这篇文章中，我们将讨论一个关于“n”鸡蛋和“k”地板的一般问题的解决方案。解决方案是尝试从每层楼（从1到k）滴下一个鸡蛋，并递归计算最坏情况下所需的最小粪便数量。在最坏的情况下给出最小值的楼层将成为解决方案的一部分。 在以下解决方案中，我们返回最坏情况下的最小试验次数；这些解决方案可以很容易地修改，以打印每个试验的楼层编号。 最坏情况场景的含义：最坏情况场景为用户提供了阈值下限的保证。例如，如果我们有“1”个鸡蛋和“k”层，我们会从一楼开始扔鸡蛋，直到鸡蛋在“k”层破裂，所以尝试给我们保证的次数是“k”。 1） 最佳子结构： 当我们从地板上扔下一个鸡蛋时，可能有两种情况（1）鸡蛋破裂（2）鸡蛋没有破裂。
- 如果鸡蛋从“x”层掉落后破裂，那么我们只需要检查低于“x”层的楼层是否有剩余的鸡蛋，因为有些楼层应该低于“x”层，鸡蛋不会破裂；因此，问题减少到x-1层和n-1个鸡蛋。
- 如果鸡蛋从“x”层掉下来后没有破裂，那么我们只需要检查高于“x”层的楼层；因此，问题归结为“k-x”层和n个鸡蛋。
因为我们需要尽量减少 最差的 例，我们最多拿两例。我们考虑最大的以上两种情况下的每一层，选择地板，从而产生最少的试验次数。
k==>楼层数 n==>蛋的数量 eggDrop（n，k）=>找到临界值所需的最小试验次数 最坏的情况是地板。 蛋液滴（n，k）=1+min{max（蛋液滴（n-1，x-1），蛋液滴（n，k-x）），其中x位于{1，2，…，k} 最坏情况的概念： 例如： 那就让这里有两个鸡蛋和两层楼吧 如果我们试着从“一楼”投掷： 最坏情况下的尝试次数=1+最大值（0,1） 0=>如果鸡蛋从一楼破裂，那么它就是门槛层（最佳情况可能性）。 1=>如果鸡蛋没有从一楼破裂，我们现在将有“2”个鸡蛋和1层进行测试，测试结果如下： ‘1’.（最坏情况的可能性） 我们考虑了最坏情况的可能性，所以1+max（0，1）=2 如果我们尝试从“二楼”投掷： 最坏情况下的尝试次数=1+最大值（1,0） 1=>如果鸡蛋从二楼破裂，那么我们将有一个鸡蛋和一个楼层来找到阈值楼层。（最坏情况） 0=>如果鸡蛋没有从第二层破裂，那么它就是门槛层。（最佳案例） 我们采用最坏情况下的可能性作为担保，所以1+max（1，0）=2。 最后的答案是min（1楼、2楼、3楼……、kth楼） 所以这里的答案是“2”。
以下是上述方法的实施情况：
C++
#include <bits/stdc++.h> using namespace std; // A utility function to get // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } // Function to get minimum // number of trials needed in worst // case with n eggs and k floors int eggDrop( int n, int k) { // If there are no floors, // then no trials needed. // OR if there is one floor, // one trial needed. if (k == 1 || k == 0) return k; // We need k trials for one // egg and k floors if (n == 1) return k; int min = INT_MAX, x, res; // Consider all droppings from // 1st floor to kth floor and // return the minimum of these // values plus 1. for (x = 1; x <= k; x++) { res = max( eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; } // Driver program to test // to printDups int main() { int n = 2, k = 10; cout << "Minimum number of trials " "in worst case with " << n << " eggs and " << k << " floors is " << eggDrop(n, k) << endl; return 0; } // This code is contributed // by Akanksha Rai |
C
#include <limits.h> #include <stdio.h> // A utility function to get // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ int eggDrop( int n, int k) { // If there are no floors, then no // trials needed. OR if there is // one floor, one trial needed. if (k == 1 || k == 0) return k; // We need k trials for one egg and // k floors if (n == 1) return k; int min = INT_MAX, x, res; // Consider all droppings from 1st // floor to kth floor and // return the minimum of these values // plus 1. for (x = 1; x <= k; x++) { res = max( eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; } /* Driver program to test to printDups*/ int main() { int n = 2, k = 10; printf ( "nMinimum number of trials in " "worst case with %d eggs and " "%d floors is %d " , n, k, eggDrop(n, k)); return 0; } |
JAVA
public class GFG { /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ static int eggDrop( int n, int k) { // If there are no floors, then // no trials needed. OR if there // is one floor, one trial needed. if (k == 1 || k == 0 ) return k; // We need k trials for one egg // and k floors if (n == 1 ) return k; int min = Integer.MAX_VALUE; int x, res; // Consider all droppings from // 1st floor to kth floor and // return the minimum of these // values plus 1. for (x = 1 ; x <= k; x++) { res = Math.max(eggDrop(n - 1 , x - 1 ), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1 ; } // Driver code public static void main(String args[]) { int n = 2 , k = 10 ; System.out.print( "Minimum number of " + "trials in worst case with " + n + " eggs and " + k + " floors is " + eggDrop(n, k)); } // This code is contributed by Ryuga. } |
Python 3
import sys # Function to get minimum number of trials # needed in worst case with n eggs and k floors def eggDrop(n, k): # If there are no floors, then no trials # needed. OR if there is one floor, one # trial needed. if (k = = 1 or k = = 0 ): return k # We need k trials for one egg # and k floors if (n = = 1 ): return k min = sys.maxsize # Consider all droppings from 1st # floor to kth floor and return # the minimum of these values plus 1. for x in range ( 1 , k + 1 ): res = max (eggDrop(n - 1 , x - 1 ), eggDrop(n, k - x)) if (res < min ): min = res return min + 1 # Driver Code if __name__ = = "__main__" : n = 2 k = 10 print ( "Minimum number of trials in worst case with" , n, "eggs and" , k, "floors is" , eggDrop(n, k)) # This code is contributed by ita_c |
C#
using System; class GFG { /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ static int eggDrop( int n, int k) { // If there are no floors, then // no trials needed. OR if there // is one floor, one trial needed. if (k == 1 || k == 0) return k; // We need k trials for one egg // and k floors if (n == 1) return k; int min = int .MaxValue; int x, res; // Consider all droppings from // 1st floor to kth floor and // return the minimum of these // values plus 1. for (x = 1; x <= k; x++) { res = Math.Max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; } // Driver code static void Main() { int n = 2, k = 10; Console.Write( "Minimum number of " + "trials in worst case with " + n + " eggs and " + k + " floors is " + eggDrop(n, k)); } } // This code is contributed by Sam007. |
Javascript
<script> /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ function eggDrop(n,k) { // If there are no floors, then // no trials needed. OR if there // is one floor, one trial needed. if (k == 1 || k == 0) return k; // We need k trials for one egg // and k floors if (n == 1) return k; let min = Number.MAX_VALUE; let x, res; // Consider all droppings from // 1st floor to kth floor and // return the minimum of these // values plus 1. for (x = 1; x <= k; x++) { res = Math.max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; } // Driver code let n = 2, k = 10; document.write( "Minimum number of " + "trials in worst case with " + n + " eggs and " + k + " floors is " + eggDrop(n, k)); // This code is contributed by avanitrachhadiya2155 </script> |
输出
Minimum number of trials in worst case with 2 eggs and 10 floors is 4
输出：
Minimum number of trials in worst case with 2 eggs and 10 floors is 4
应该注意的是，上面的函数一次又一次地计算相同的子问题。参见下面的部分递归树，E（2，2）被计算了两次。当你绘制完整的递归树时，即使是对于n和k的小值，也会有许多重复的子问题。
E(2, 4) | ------------------------------------- | | | | | | | | x=1/ x=2/ x=3/ x=4/ / / .... .... / / E(1, 0) E(2, 3) E(1, 1) E(2, 2) / /... / x=1/ ..... / E(1, 0) E(2, 2) / ......Partial recursion tree for 2 eggs and 4 floors.
复杂性分析：
- 时间复杂性： 由于存在子问题重叠的情况，时间复杂度是指数级的。
- 辅助空间： O（1）。因为没有使用任何数据结构来存储值。
由于再次调用相同的子问题，此问题具有重叠子问题属性。因此，鸡蛋掉落谜题有两个属性（参见 这 和 这 )一个动态规划问题。像其他典型的 动态规划问题 ，通过以自下而上的方式构造临时数组eggfool[]可以避免相同子问题的重新计算。 方法2 : 动态规划。 在这种方法中，我们的工作原理与上述相同 忽略了反复计算子问题答案的情况。 。方法是制作一个表格，存储子问题的结果，以便解决子问题，只需从表格中查找 恒定时间 ，早些时候 指数时间 . 正式填写DP[i][j]时，说明其中“i”是鸡蛋的数量，“j”是楼层的数量：
- 我们必须从’1’到’j’遍历每个楼层的’x’，并找到以下最小值：
(1 + max( DP[i-1][j-1], DP[i][j-x] )).
这一模拟将使事情变得清楚：
i=>鸡蛋数量 j=>楼层数 查找最大值 让我们填写以下情况的表格： 楼层=’4′ 鸡蛋=’2′ 1 2 3 4 1 2 3 4 => 1 1 2 2 3 => 2 对于“egg-1”，每个案例都是基本案例，因此 尝试次数等于楼层数。 对于“蛋-2”，第一次需要“1”次尝试 地板是基本情况。 对于2楼=> 第一层1+最大值（0，DP[1][1]） 第二层1+最大值（DP[1][1]，0） DP[2][2]=min（1+max（0，DP[1][1]），1+max（DP[1][1]，0）） 对于3楼=> 第一层1+最大值（0，DP[2][2]） 在二楼1+最多（DP[1][1]，DP[2][1]） 3楼1+最大值（0，DP[2][2]） DP[2][3]=min（‘所有三层楼’）=2 对于4楼=> 第一层1+最大值（0，DP[2][3]） 在二楼1+最多（DP[1][1]，DP[2][2]） 在三楼1+最多（DP[1][2]，DP[2][1]） 第四层1+最大值（0，DP[2][3]） DP[2][4]=最小值（“全部四层楼”）=3
C++
// A Dynamic Programming based for // the Egg Dropping Puzzle #include <bits/stdc++.h> using namespace std; // A utility function to get // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ int eggDrop( int n, int k) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ int eggFloor[n + 1][k + 1]; int res; int i, j, x; // We need one trial for one floor and 0 // trials for 0 floors for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } // We always need j trials for one egg // and j floors. for (j = 1; j <= k; j++) eggFloor[1][j] = j; // Fill rest of the entries in table using // optimal substructure property for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = INT_MAX; for (x = 1; x <= j; x++) { res = 1 + max( eggFloor[i - 1][x - 1], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n][k]; } /* Driver program to test to printDups*/ int main() { int n = 2, k = 36; cout << "Minimum number of trials " "in worst case with " << n<< " eggs and " << k<< " floors is " << eggDrop(n, k); return 0; } // this code is contributed by shivanisinghss2110 |
C
// A Dynamic Programming based for // the Egg Dropping Puzzle #include <limits.h> #include <stdio.h> // A utility function to get // maximum of two integers int max( int a, int b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ int eggDrop( int n, int k) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ int eggFloor[n + 1][k + 1]; int res; int i, j, x; // We need one trial for one floor and 0 // trials for 0 floors for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } // We always need j trials for one egg // and j floors. for (j = 1; j <= k; j++) eggFloor[1][j] = j; // Fill rest of the entries in table using // optimal substructure property for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = INT_MAX; for (x = 1; x <= j; x++) { res = 1 + max( eggFloor[i - 1][x - 1], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n][k]; } /* Driver program to test to printDups*/ int main() { int n = 2, k = 36; printf ( "Minimum number of trials " "in worst case with %d eggs and " "%d floors is %d " , n, k, eggDrop(n, k)); return 0; } |
JAVA
// A Dynamic Programming based Java // Program for the Egg Dropping Puzzle class EggDrop { // A utility function to get // maximum of two integers static int max( int a, int b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ static int eggDrop( int n, int k) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ int eggFloor[][] = new int [n + 1 ][k + 1 ]; int res; int i, j, x; // We need one trial for one floor and // 0 trials for 0 floors for (i = 1 ; i <= n; i++) { eggFloor[i][ 1 ] = 1 ; eggFloor[i][ 0 ] = 0 ; } // We always need j trials for one egg // and j floors. for (j = 1 ; j <= k; j++) eggFloor[ 1 ][j] = j; // Fill rest of the entries in table using // optimal substructure property for (i = 2 ; i <= n; i++) { for (j = 2 ; j <= k; j++) { eggFloor[i][j] = Integer.MAX_VALUE; for (x = 1 ; x <= j; x++) { res = 1 + max( eggFloor[i - 1 ][x - 1 ], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n][k]; } /* Driver program to test to printDups*/ public static void main(String args[]) { int n = 2 , k = 10 ; System.out.println( "Minimum number of trials in worst" + " case with " + n + " eggs and " + k + " floors is " + eggDrop(n, k)); } } /*This code is contributed by Rajat Mishra*/ |
Python3
# A Dynamic Programming based Python Program for the Egg Dropping Puzzle INT_MAX = 32767 # Function to get minimum number of trials needed in worst # case with n eggs and k floors def eggDrop(n, k): # A 2D table where entry eggFloor[i][j] will represent minimum # number of trials needed for i eggs and j floors. eggFloor = [[ 0 for x in range (k + 1 )] for x in range (n + 1 )] # We need one trial for one floor and0 trials for 0 floors for i in range ( 1 , n + 1 ): eggFloor[i][ 1 ] = 1 eggFloor[i][ 0 ] = 0 # We always need j trials for one egg and j floors. for j in range ( 1 , k + 1 ): eggFloor[ 1 ][j] = j # Fill rest of the entries in table using optimal substructure # property for i in range ( 2 , n + 1 ): for j in range ( 2 , k + 1 ): eggFloor[i][j] = INT_MAX for x in range ( 1 , j + 1 ): res = 1 + max (eggFloor[i - 1 ][x - 1 ], eggFloor[i][j - x]) if res < eggFloor[i][j]: eggFloor[i][j] = res # eggFloor[n][k] holds the result return eggFloor[n][k] # Driver program to test to print printDups n = 2 k = 36 print ( "Minimum number of trials in worst case with" + str (n) + "eggs and " + str (k) + " floors is " + str (eggDrop(n, k))) # This code is contributed by Bhavya Jain |
C#
// A Dynamic Programming based C# Program // for the Egg Dropping Puzzle using System; class GFG { // A utility function to get maximum of // two integers static int max( int a, int b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ static int eggDrop( int n, int k) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ int [, ] eggFloor = new int [n + 1, k + 1]; int res; int i, j, x; // We need one trial for one floor and0 // trials for 0 floors for (i = 1; i <= n; i++) { eggFloor[i, 1] = 1; eggFloor[i, 0] = 0; } // We always need j trials for one egg // and j floors. for (j = 1; j <= k; j++) eggFloor[1, j] = j; // Fill rest of the entries in table // using optimal substructure property for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i, j] = int .MaxValue; for (x = 1; x <= j; x++) { res = 1 + max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]); if (res < eggFloor[i, j]) eggFloor[i, j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n, k]; } // Driver function public static void Main() { int n = 2, k = 36; Console.WriteLine( "Minimum number of trials " + "in worst case with " + n + " eggs and " + k + "floors is " + eggDrop(n, k)); } } // This code is contributed by Sam007. |
PHP
<?php // A Dynamic Programming based PHP // Program for the Egg Dropping Puzzle /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ function eggDrop( $n , $k ) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ $eggFloor = array ( array ());; // We need one trial for one // floor and0 trials for 0 floors for ( $i = 1; $i <= $n ; $i ++) { $eggFloor [ $i ][1] = 1; $eggFloor [ $i ][0] = 0; } // We always need j trials // for one egg and j floors. for ( $j = 1; $j <= $k ; $j ++) $eggFloor [1][ $j ] = $j ; // Fill rest of the entries in // table using optimal substructure // property for ( $i = 2; $i <= $n ; $i ++) { for ( $j = 2; $j <= $k ; $j ++) { $eggFloor [ $i ][ $j ] = 999999; for ( $x = 1; $x <= $j ; $x ++) { $res = 1 + max( $eggFloor [ $i - 1][ $x - 1], $eggFloor [ $i ][ $j - $x ]); if ( $res < $eggFloor [ $i ][ $j ]) $eggFloor [ $i ][ $j ] = $res ; } } } // eggFloor[n][k] holds the result return $eggFloor [ $n ][ $k ]; } // Driver Code $n = 2; $k = 36; echo "Minimum number of trials in worst case with " . $n . " eggs and " . $k . " floors is " .eggDrop( $n , $k ) ; // This code is contributed by Sam007 ?> |
Javascript
<script> // A Dynamic Programming based Javascript // Program for the Egg Dropping Puzzle // A utility function to get // maximum of two integers function max(a,b) { return (a > b) ? a : b; } /* Function to get minimum number of trials needed in worst case with n eggs and k floors */ function eggDrop(n,k) { /* A 2D table where entry eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ let eggFloor = new Array(n + 1); for (let i=0;i<(n+1);i++) { eggFloor[i]= new Array(k+1); } let res; let i, j, x; // We need one trial for one floor and // 0 trials for 0 floors for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } // We always need j trials for one egg // and j floors. for (j = 1; j <= k; j++) eggFloor[1][j] = j; // Fill rest of the entries in table using // optimal substructure property for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = Number.MAX_VALUE; for (x = 1; x <= j; x++) { res = 1 + max( eggFloor[i - 1][x - 1], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n][k]; } /* Driver program to test to printDups*/ let n = 2, k = 36; document.write( "Minimum number of trials in worst" + " case with " + n + " eggs and " + k + " floors is " + eggDrop(n, k)); // This code is contributed by ab2127 </script> |
输出
Minimum number of trials in worst case with 2 eggs and 36 floors is 8
复杂性分析：
- 时间复杂性： O（n*k^2）。 其中“n”是鸡蛋的数量，“k”是楼层的数量，因为我们对每个鸡蛋使用嵌套for循环“k^2”次
- 辅助空间： O（n*k）。 因为大小为“n*k”的二维数组用于存储元素。
方法3： 使用记忆的动态规划。
C++
#include <bits/stdc++.h> using namespace std; #define MAX 1000 vector<vector< int >> memo(MAX, vector< int > (MAX, -1)); int solveEggDrop( int n, int k) { if (memo[n][k] != -1) { return memo[n][k];} if (k == 1 || k == 0) return k; if (n == 1) return k; int min = INT_MAX, x, res; for (x = 1; x <= k; x++) { res = max( solveEggDrop(n - 1, x - 1), solveEggDrop(n, k - x)); if (res < min) min = res; } memo[n][k] = min+1; return min + 1; } int main() { int n = 2, k = 36; cout<<solveEggDrop(n, k); return 0; } // contributed by Shivam Agrawal(shivamagrawal3) |
JAVA
import java.util.Arrays; class GFG { static final int MAX = 1000 ; static int [][] memo = new int [MAX][MAX]; static int solveEggDrop( int n, int k) { if (memo[n][k] != - 1 ) { return memo[n][k]; } if (k == 1 || k == 0 ) return k; if (n == 1 ) return k; int min = Integer.MAX_VALUE, x, res; for (x = 1 ; x <= k; x++) { res = Math.max(solveEggDrop(n - 1 , x - 1 ), solveEggDrop(n, k - x)); if (res < min) min = res; } memo[n][k] = min + 1 ; return min + 1 ; } public static void main(String[] args) { for ( int i = 0 ; i < memo.length; i++) Arrays.fill(memo[i], - 1 ); int n = 2 , k = 36 ; System.out.print(solveEggDrop(n, k)); } } // This code IS contributed by umadevi9616 |
Python3
import sys MAX = 1000 ; memo = [[ - 1 for i in range ( MAX )] for j in range ( MAX )] ; def solveEggDrop(n, k): if (memo[n][k] ! = - 1 ): return memo[n][k]; if (k = = 1 or k = = 0 ): return k; if (n = = 1 ): return k; min = sys.maxsize; res = 0 ; for x in range ( 1 ,k + 1 ): res = max (solveEggDrop(n - 1 , x - 1 ), solveEggDrop(n, k - x)); if (res < min ): min = res; memo[n][k] = min + 1 ; return min + 1 ; # Driver code if __name__ = = '__main__' : n = 2 ; k = 36 ; print (solveEggDrop(n, k)); # This code is contributed by gauravrajput1 |
C#
using System; public class GFG { static readonly int MAX = 1000; static int [,] memo = new int [MAX,MAX]; static int solveEggDrop( int n, int k) { if (memo[n,k] != -1) { return memo[n,k]; } if (k == 1 || k == 0) return k; if (n == 1) return k; int min = int .MaxValue, x, res; for (x = 1; x <= k; x++) { res = Math.Max(solveEggDrop(n - 1, x - 1), solveEggDrop(n, k - x)); if (res < min) min = res; } memo[n,k] = min + 1; return min + 1; } public static void Main(String[] args) { for ( int i = 0; i < memo.GetLength(0); i++) for ( int j =0;j<memo.GetLength(1);j++) memo[i,j] = -1; int n = 2, k = 36; Console.Write(solveEggDrop(n, k)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> var MAX = 1000; var memo = Array(MAX).fill().map(()=>Array(MAX).fill(-1)); function solveEggDrop(n , k) { if (memo[n][k] != -1) { return memo[n][k]; } if (k == 1 || k == 0) return k; if (n == 1) return k; var min = Number.MAX_VALUE, x, res; for (x = 1; x <= k; x++) { res = Math.max(solveEggDrop(n - 1, x - 1), solveEggDrop(n, k - x)); if (res < min) min = res; } memo[n][k] = min + 1; return min + 1; } var n = 2, k = 36; document.write(solveEggDrop(n, k)); // This code is contributed by gauravrajput1 </script> |
输出
8
作为练习，您可以尝试修改上述DP解决方案，以打印所有中间楼层（用于最低试用解决方案的楼层）。 更有效的解决方案 : 丢蛋难题（二项式系数和二进制搜索解） 2个鸡蛋和K层的鸡蛋掉落拼图 2个鸡蛋和100层拼图
&t=3s 参考资料： http://archive.ite.journal.informs.org/Vol4No1/Sniedovich/index.php 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
