text: Egg Dropping Puzzle | DP | A Dynamic Programming based for the Egg Dropping Puzzle ; A utility 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
code: #include <limits.h> NEW_LINE #include <stdio.h> NEW_LINE int max ( int a , int b ) { return ( a > b ) ? a : b ; } int eggDrop ( int n , int k ) { int eggFloor [ n + 1 ] [ k + 1 ] ; int res ; int 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 ] = 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 ; } } } return eggFloor [ n ] [ k ] ; } int main ( ) { int n = 2 , k = 36 ; printf ( " Minimum number of trials " STRNEWLINE TABSYMBOL TABSYMBOL " in worst case with % d eggs and " STRNEWLINE TABSYMBOL TABSYMBOL " % d floors is % d " , n , k , eggDrop ( n , k ) ) ; return 0 ; }