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
def minStepsRecur ( height , l , r , h ) : NEW_LINE INDENT if l >= r : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT m = l NEW_LINE for i in range ( l , r ) : NEW_LINE INDENT if height [ i ] < height [ m ] : NEW_LINE INDENT m = i NEW_LINE DEDENT DEDENT return min ( r - l , minStepsRecur ( height , l , m , height [ m ] ) + minStepsRecur ( height , m + 1 , r , height [ m ] ) + height [ m ] - h ) NEW_LINE DEDENT def minSteps ( height , N ) : NEW_LINE INDENT return minStepsRecur ( height , 0 , N , 0 ) NEW_LINE DEDENT height = [ 2 , 1 , 2 , 5 , 1 ] NEW_LINE N = len ( height ) NEW_LINE print ( minSteps ( height , N ) ) NEW_LINE