Egg Dropping Puzzle | DP | A Dynamic Programming based Python Program for the Egg Dropping Puzzle ; Function to get minimum number of trials needed in worst case with n eggs and k floors ; A 2D table where entry eggFloor [ i ] [ j ] will represent minimum number of trials needed for i eggs and j floors . ; We need one trial for one floor and0 trials for 0 floors ; We always need j trials for one egg and j floors . ; Fill rest of the entries in table using optimal substructure property ; eggFloor [ n ] [ k ] holds the result ; Driver program to test to pront printDups
INT_MAX = 32767 NEW_LINE def eggDrop ( n , k ) : NEW_LINE INDENT eggFloor = [ [ 0 for x in range ( k + 1 ) ] for x in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT eggFloor [ i ] [ 1 ] = 1 NEW_LINE eggFloor [ i ] [ 0 ] = 0 NEW_LINE DEDENT for j in range ( 1 , k + 1 ) : NEW_LINE INDENT eggFloor [ 1 ] [ j ] = j NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 2 , k + 1 ) : NEW_LINE INDENT eggFloor [ i ] [ j ] = INT_MAX NEW_LINE for x in range ( 1 , j + 1 ) : NEW_LINE INDENT res = 1 + max ( eggFloor [ i - 1 ] [ x - 1 ] , eggFloor [ i ] [ j - x ] ) NEW_LINE if res < eggFloor [ i ] [ j ] : NEW_LINE INDENT eggFloor [ i ] [ j ] = res NEW_LINE DEDENT DEDENT DEDENT DEDENT return eggFloor [ n ] [ k ] NEW_LINE DEDENT n = 2 NEW_LINE k = 36 NEW_LINE print ( " Minimum ▁ number ▁ of ▁ trials ▁ in ▁ worst ▁ case ▁ with " + str ( n ) + " eggs ▁ and ▁ " + str ( k ) + " ▁ floors ▁ is ▁ " + str ( eggDrop ( n , k ) ) ) NEW_LINE