Minimum sum of multiplications of n numbers | Java program to find the minimum sum of multiplication 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
import java . io . * ; import java . math . * ; class GFG { static long dp [ ] [ ] = new long [ 1000 ] [ 1000 ] ; static long sum ( int a [ ] , int i , int j ) { long ans = 0 ; for ( int m = i ; m <= j ; m ++ ) ans = ( ans + a [ m ] ) % 100 ; return ans ; } static long solve ( int a [ ] , int i , int j ) { if ( i == j ) return 0 ; if ( dp [ i ] [ j ] != - 1 ) return dp [ i ] [ j ] ; dp [ i ] [ j ] = 100000000 ; for ( int 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 ] ; } static void initialize ( int n ) { for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j <= n ; j ++ ) dp [ i ] [ j ] = - 1 ; } public static void main ( String args [ ] ) { int a [ ] = { 40 , 60 , 20 } ; int n = a . length ; initialize ( n ) ; System . out . println ( solve ( a , 0 , n - 1 ) ) ; } }