N consecutive ropes problem | Java 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 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
class GFG { static int MinCost ( int arr [ ] , int n ) { int [ ] [ ] dp = new int [ n + 5 ] [ n + 5 ] ; int [ ] [ ] sum = new int [ n + 5 ] [ n + 5 ] ; 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 ] = Integer . MAX_VALUE ; if ( i == j ) dp [ i ] [ j ] = 0 ; else { for ( int 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 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 7 , 6 , 8 , 6 , 1 , 1 } ; int n = arr . length ; System . out . println ( MinCost ( arr , n ) ) ; } }