Egg Dropping Puzzle | DP | A function to get maximum of two integers ; 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 and 0 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
function max ( a , b ) { return ( a > b ) ? a : b ; } function eggDrop ( n , k ) { 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 ; for ( i = 1 ; i <= n ; i ++ ) { eggFloor [ i ] [ 1 ] = 1 ; eggFloor [ i ] [ 0 ] = 0 ; } for ( j = 1 ; j <= k ; j ++ ) eggFloor [ 1 ] [ j ] = j ; 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 ; } } } return eggFloor [ n ] [ k ] ; } let n = 2 , k = 36 ; document . write ( " " + " " + n + " " + k + " " + eggDrop ( n , k ) ) ;