N consecutive ropes problem | Function to return the minimum cost to connect the given ropes ; dp [ i ] [ j ] = minimum cost in range ( i , j ) sum [ i ] [ j ] = sum of range ( i , j ) ; Initializing the sum table memset ( sum , 0 , sizeof ( 0 ) ) ; ; Computing minimum cost for all the possible interval ( i , j ) Left range ; Right range ; No cost for a single rope ; Driver code
def MinCost ( arr , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 5 ) ] for i in range ( n + 5 ) ] NEW_LINE sum = [ [ 0 for i in range ( n + 5 ) ] for i in range ( n + 5 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT k = arr [ i ] NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT sum [ i ] [ j ] = k NEW_LINE DEDENT else : NEW_LINE INDENT k += arr [ j ] NEW_LINE sum [ i ] [ j ] = k NEW_LINE DEDENT DEDENT DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( i , n ) : NEW_LINE INDENT dp [ i ] [ j ] = 10 ** 9 NEW_LINE if ( i == j ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT for k in range ( i , j ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k + 1 ] [ j ] + sum [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ 0 ] [ n - 1 ] NEW_LINE DEDENT arr = [ 7 , 6 , 8 , 6 , 1 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( MinCost ( arr , n ) ) NEW_LINE