Minimum sum of multiplications of n numbers | Used in recursive memoized solution ; function to calculate the cumulative sum from a [ i ] to a [ j ] ; base case ; memoization , if the partition has been called before then return the stored value ; store a max value ; we break them into k partitions ; store the min of the formula thus obtained ; return the minimum ; Driver code
var dp = Array . from ( Array ( 1000 ) , ( ) => Array ( 1000 ) ) ; function sum ( a , i , j ) { var ans = 0 ; for ( var m = i ; m <= j ; m ++ ) ans = ( ans + a [ m ] ) % 100 ; return ans ; } function solve ( a , i , j ) { if ( i == j ) return 0 ; if ( dp [ i ] [ j ] != - 1 ) return dp [ i ] [ j ] ; dp [ i ] [ j ] = 1000000000 ; for ( var k = i ; k < j ; k ++ ) { dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , ( solve ( a , i , k ) + solve ( a , k + 1 , j ) + ( sum ( a , i , k ) * sum ( a , k + 1 , j ) ) ) ) ; } return dp [ i ] [ j ] ; } function initialize ( n ) { for ( var i = 0 ; i <= n ; i ++ ) for ( var j = 0 ; j <= n ; j ++ ) dp [ i ] [ j ] = - 1 ; } var a = [ 40 , 60 , 20 ] ; var n = a . length ; initialize ( n ) ; document . write ( solve ( a , 0 , n - 1 ) ) ;