Egg Dropping Puzzle | DP | 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 Code
< ? php function eggDrop ( $ n , $ k ) { $ eggFloor = array ( array ( ) ) ; ; 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 ] = 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 ; } } } return $ eggFloor [ $ n ] [ $ k ] ; } $ n = 2 ; $ k = 36 ; echo " Minimum ▁ number ▁ of ▁ trials ▁ in ▁ worst ▁ case ▁ with ▁ " . $ n . " ▁ eggs ▁ and ▁ " . $ k . " ▁ floors ▁ is ▁ " . eggDrop ( $ n , $ k ) ; ? >