Minimum cost of reducing Array by merging any adjacent elements repetitively | C # program for the above approach ; Function to find the total minimum cost of merging two consecutive numbers ; Find the size of numbers [ ] ; If array is empty , return 0 ; To store the prefix Sum of numbers array numbers [ ] ; Traverse numbers [ ] to find the prefix sum ; dp table to memoised the value ; Iterate for length >= 1 ; Find sum in range [ i . . j ] ; Initialise dp [ i , j ] to int . MaxValue ; Iterate for all possible K to find the minimum cost ; Update the minimum sum ; Return the readonly minimum cost ; Driver Code ; Given set of numbers ; Function Call
using System ; class GFG { static int mergeTwoNumbers ( int [ ] numbers ) { int len , i , j , k ; int n = numbers . Length ; if ( numbers . Length == 0 ) { return 0 ; } int [ ] prefixSum = new int [ n + 1 ] ; for ( i = 1 ; i <= n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + numbers [ i - 1 ] ; } int [ , ] dp = new int [ n + 1 , n + 1 ] ; for ( len = 2 ; len <= n ; len ++ ) { for ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; int sum = prefixSum [ j ] - prefixSum [ i - 1 ] ; dp [ i , j ] = int . MaxValue ; for ( k = i ; k < j ; k ++ ) { dp [ i , j ] = Math . Min ( dp [ i , j ] , dp [ i , k ] + dp [ k + 1 , j ] + sum ) ; } } } return dp [ 1 , n ] ; } public static void Main ( String [ ] args ) { int [ ] arr1 = { 6 , 4 , 4 , 6 } ; Console . Write ( mergeTwoNumbers ( arr1 ) + " STRNEWLINE " ) ; } }