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
function MinCost ( arr , n ) { let dp = new Array ( n + 5 ) ; let sum = new Array ( n + 5 ) ; for ( let i = 0 ; i < n + 5 ; i ++ ) { dp [ i ] = [ ] ; sum [ i ] = [ ] ; for ( let j = 0 ; j < n + 5 ; j ++ ) { dp [ i ] . push ( 0 ) sum [ i ] . push ( 0 ) } } console . log ( dp ) for ( let i = 0 ; i < n ; i ++ ) { let k = arr [ i ] ; for ( let j = i ; j < n ; j ++ ) { if ( i == j ) sum [ i ] [ j ] = k ; else { k += arr [ j ] ; sum [ i ] [ j ] = k ; } } } for ( let i = n - 1 ; i >= 0 ; i -- ) { for ( let j = i ; j < n ; j ++ ) { dp [ i ] [ j ] = Number . MAX_SAFE_INTEGER ; if ( i == j ) dp [ i ] [ j ] = 0 ; else { for ( let k = i ; k < j ; k ++ ) { dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k + 1 ] [ j ] + sum [ i ] [ j ] ) ; } } } } return dp [ 0 ] [ n - 1 ] ; } let arr = [ 7 , 6 , 8 , 6 , 1 , 1 ] ; let n = arr . length ; document . write ( MinCost ( arr , n ) ) ;