Collect all coins in minimum number of steps | Java Code to 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 program to test above function
import java . util . * ; class GFG { public static int minStepsRecur ( int height [ ] , int l , int r , int h ) { if ( l >= r ) return 0 ; int m = l ; for ( int i = l ; i < r ; i ++ ) if ( height [ i ] < height [ m ] ) m = i ; return Math . min ( r - l , minStepsRecur ( height , l , m , height [ m ] ) + minStepsRecur ( height , m + 1 , r , height [ m ] ) + height [ m ] - h ) ; } public static int minSteps ( int height [ ] , int N ) { return minStepsRecur ( height , 0 , N , 0 ) ; } public static void main ( String [ ] args ) { int height [ ] = { 2 , 1 , 2 , 5 , 1 } ; int N = height . length ; System . out . println ( minSteps ( height , N ) ) ; } }