text: N consecutive ropes problem | C ++ implementation of the approach ; 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 ; Computing minimum cost for all the possible interval ( i , j ) Left range ; Right range ; No cost for a single rope ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int MinCost ( int arr [ ] , int n ) { int dp [ n + 5 ] [ n + 5 ] , sum [ n + 5 ] [ n + 5 ] ; memset ( sum , 0 , sizeof ( 0 ) ) ; for ( int i = 0 ; i < n ; i ++ ) { int k = arr [ i ] ; for ( int j = i ; j < n ; j ++ ) { if ( i == j ) sum [ i ] [ j ] = k ; else { k += arr [ j ] ; sum [ i ] [ j ] = k ; } } } for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = i ; j < n ; j ++ ) { dp [ i ] [ j ] = INT_MAX ; if ( i == j ) dp [ i ] [ j ] = 0 ; else { for ( int k = i ; k < j ; k ++ ) { dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k + 1 ] [ j ] + sum [ i ] [ j ] ) ; } } } } return dp [ 0 ] [ n - 1 ] ; } int main ( ) { int arr [ ] = { 7 , 6 , 8 , 6 , 1 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << MinCost ( arr , n ) ; return 0 ; }