Collect all coins in minimum number of steps | recursive method to collect coins from height array l to r , with height h already collected ; if l is more than r , no steps needed ; loop over heights to get minimum height index ; choose minimum from , 1 ) collecting coins using all vertical lines ( total r - l ) 2 ) collecting coins using lower horizontal lines and recursively on left and right segments ; method returns minimum number of step to collect coin from stack , with height in height [ ] array ; Driver Code
< ? php function minStepsRecur ( $ height , $ l , $ r , $ h ) { if ( $ l >= $ r ) return 0 ; $ m = $ l ; for ( $ i = $ l ; $ i < $ r ; $ i ++ ) if ( $ height [ $ i ] < $ height [ $ m ] ) $ m = $ i ; return min ( $ r - $ l , minStepsRecur ( $ height , $ l , $ m , $ height [ $ m ] ) + minStepsRecur ( $ height , $ m + 1 , $ r , $ height [ $ m ] ) + $ height [ $ m ] - $ h ) ; } function minSteps ( $ height , $ N ) { return minStepsRecur ( $ height , 0 , $ N , 0 ) ; } $ height = array ( 2 , 1 , 2 , 5 , 1 ) ; $ N = sizeof ( $ height ) ; echo minSteps ( $ height , $ N ) ; ? >