# Minimum sum of multiplications of n numbers

Given n integers. The task is to minimize the sum of multiplication of all the numbers by taking two adjacent numbers at a time and putting back their sum % 100 till a number is left.

Examples :

```Input : 40 60 20
Output : 2400
Explanation: There are two possible cases:
1st possibility: Take 40 and 60, so multiplication=2400
and put back (60+40) % 100 = 0, making it 0, 20.
Multiplying 0 and 20 we get 0 so
multiplication = 2400+0 = 2400. Put back (0+20)%100 = 20.
2nd possibility: take 60 and 20, so 60*20 = 1200,
put back (60+20)%100 = 80, making it [40, 80]
multiply 40*80 to get 3200, so multiplication
sum = 1200+3200 = 4400. Put back (40+80)%100 = 20

Input : 5 6
Output : 30
Explanation: Only possibility is 5*6=30
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: The problem is a variation of Matrix chain Multiplication Dynamic Programming

The idea is to partition N numbers into every possible value of k. Solve recursively for smaller parts and add the multiplication and store the minimum of them. Since we are dividing it into k parts, for every DPi,j we will have k partitions i<=k<j , store the minimum of them. So we get the formula similar to Matrix chain Multiplication Dynamic Programming.

DPi,j = min(DPi,j , (DPi,k+DPk+1,j+(cumulative_sumi,k*cumulative_sumk+1,j) ) )
for every i<=k<j.

Since many subproblems will be repeating, hence we use memoization to store the values in a nXn matrix.

Given below is the illustration of the above approach:

## C++

 `// CPP program to find the  ` `// minimum sum of multiplication ` `// of n numbers ` `#include ` `using` `namespace` `std; ` ` `  `// Used in recursive  ` `// memoized solution ` `long` `long` `dp; ` ` `  `// function to calculate the cumulative  ` `// sum from a[i] to a[j] ` `long` `long` `sum(``int` `a[], ``int` `i, ``int` `j) ` `{      ` `    ``long` `long` `ans = 0; ` `    ``for` `(``int` `m = i; m <= j; m++)      ` `        ``ans = (ans + a[m]) % 100; ` `    ``return` `ans; ` `} ` ` `  `long` `long` `solve(``int` `a[], ``int` `i, ``int` `j) ` `{ ` `    ``// base case  ` `    ``if` `(i == j) ` `        ``return` `0;  ` `     `  `    ``// memoization, if the partition  ` `    ``// has been called before then  ` `    ``// return the stored value  ` `    ``if` `(dp[i][j] != -1) ` `        ``return` `dp[i][j]; ` `     `  `    ``// store a max value  ` `    ``dp[i][j] = INT_MAX; ` `     `  `    ``// we break them into k partitions  ` `    ``for` `(``int` `k = i; k < j; k++) ` `    ``{ ` `        ``// store the min of the  ` `        ``// formula thus obtained ` `        ``dp[i][j] = min(dp[i][j], (solve(a, i, k) + ` `                              ``solve(a, k + 1, j) +  ` `              ``(sum(a, i, k) * sum(a, k + 1, j)))); ` `    ``} ` `     `  `    ``// return the minimum  ` `    ``return` `dp[i][j]; ` `} ` ` `  `void` `intialize(``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i <= n; i++)  ` `        ``for` `(``int` `j = 0; j <= n; j++) ` `            ``dp[i][j] = -1;      ` `} ` ` `  `// Driver code  ` `int` `main() { ` `    ``int` `a[] = {40, 60, 20};  ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a); ` `    ``intialize(n); ` `    ``cout << solve(a, 0, n - 1) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find the   ` `// minimum sum of multiplication ` `// of n numbers ` `import` `java.io.*; ` `import` `java.math.*; ` ` `  ` `  `class` `GFG ` `{ ` `     `  `    ``// Used in recursive ` `    ``// memoized solution ` `    ``static` `long` `dp[][] = ``new` `long``[``1000``][``1000``]; ` `     `  `    ``// function to calculate the  ` `    ``// cumulative  sum from a[i] to a[j] ` `    ``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) ` `    ``{ ` `        ``// base case  ` `        ``if` `(i == j) ` `            ``return` `0``;  ` `         `  `        ``// memoization, if the partition  ` `        ``// has been called before then  ` `        ``// return the stored value  ` `        ``if` `(dp[i][j] != -``1``) ` `            ``return` `dp[i][j]; ` `         `  `        ``// store a max value  ` `        ``dp[i][j] = ``100000000``; ` `         `  `        ``// we break them into k partitions  ` `        ``for` `(``int` `k = i; k < j; k++) ` `        ``{ ` `            ``// store the min of the ` `            ``// formula thus obtained ` `            ``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 the minimum  ` `        ``return` `dp[i][j]; ` `    ``} ` `     `  `    ``static` `void` `intialize(``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i <= n; i++)  ` `            ``for` `(``int` `j = ``0``; j <= n; j++) ` `                ``dp[i][j] = -``1``;      ` `    ``} ` `     `  `    ``// Driver code  ` `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `        ``int` `a[] = {``40``, ``60``, ``20``};  ` `        ``int` `n = a.length; ` `        ``intialize(n); ` `        ``System.out.println(solve(a, ``0``, n - ``1``)); ` `         `  `    ``} ` `} ` ` `  `/*This code is contributed by Nikita Tiwari.*/`

## Python3

 `# Python3 program to find the  ` `# minimum sum of multiplication  ` `# of n numbers  ` ` `  `import` `numpy as np ` `import` `sys ` ` `  `# Used in recursive  ` `# memoized solution  ` `dp ``=` `np.zeros((``1000``,``1000``))  ` ` `  `# function to calculate the cumulative  ` `# sum from a[i] to a[j]  ` `def` `sum``(a, i, j) : ` `         `  `    ``ans ``=` `0` `    ``for` `m ``in` `range``(i, j ``+` `1``) :  ` `        ``ans ``=` `(ans ``+` `a[m]) ``%` `100` `         `  `    ``return` `ans ` ` `  ` `  `def` `solve(a, i, j) : ` ` `  `    ``# base case  ` `    ``if` `(i ``=``=` `j) :  ` `        ``return` `0` `     `  `    ``# memoization, if the partition  ` `    ``# has been called before then  ` `    ``# return the stored value  ` `    ``if` `(dp[i][j] !``=` `-``1``) : ` `                 `  `        ``return` `dp[i][j]  ` `     `  `    ``# store a max value  ` `    ``dp[i][j] ``=` `sys.maxsize ` `     `  `    ``# we break them into k partitions  ` `    ``for` `k ``in` `range``(i, j) : ` `                 `  `        ``# store the min of the  ` `        ``# formula thus obtained  ` `        ``dp[i][j] ``=` `min``(dp[i][j], (solve(a, i, k) ``+` `solve(a, k ``+` `1``, j)  ` `                                ``+` `(``sum``(a, i, k) ``*` `sum``(a, k ``+` `1``, j))))  ` `     `  `    ``# return the minimum  ` `    ``return` `dp[i][j] ` ` `  ` `  `def` `intialize(n) : ` `         `  `    ``for` `i ``in` `range``(n ``+` `1``) : ` `        ``for` `j ``in` `range``(n ``+` `1``) : ` `            ``dp[i][j] ``=` `-``1`    ` `  `#Driver code  ` `if` `__name__ ``=``=` `"__main__"` `: ` `         `  `    ``a ``=` `[``40``, ``60``, ``20``] ` `    ``n ``=` `len``(a)  ` `    ``intialize(n) ` `    ``print``(``int``(solve(a, ``0``, n ``-` `1``)))  ` ` `  `# This code is contributed by Ryuga `

## C#

 `// C# program to find the  ` `// minimum sum of multiplication  ` `// of n numbers ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `     `  `    ``// Used in recursive  ` `    ``// memoized solution ` `    ``static` `long` `[,]dp = ``new` `long``[1000, 1000]; ` `     `  `    ``// Function to calculate the cumulative  ` `    ``// sum from a[i] to a[j] ` `    ``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) ` `    ``{ ` `        ``// base case  ` `        ``if` `(i == j) ` `            ``return` `0;  ` `         `  `        ``// memoization, if the partition  ` `        ``// has been called before then  ` `        ``// return the stored value  ` `        ``if` `(dp[i, j] != -1) ` `            ``return` `dp[i, j]; ` `         `  `        ``// store a max value  ` `        ``dp[i, j] = 100000000; ` `         `  `        ``// we break them into k partitions  ` `        ``for` `(``int` `k = i; k < j; k++) ` `        ``{ ` `            ``// store the min of the  ` `            ``// formula thus obtained ` `            ``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 the minimum  ` `        ``return` `dp[i, j]; ` `    ``} ` `     `  `    ``static` `void` `intialize(``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = 0; i <= n; i++)  ` `            ``for` `(``int` `j = 0; j <= n; j++) ` `                ``dp[i, j] = -1;  ` `    ``} ` `     `  `    ``// Driver code  ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``int` `[]a = {40, 60, 20};  ` `        ``int` `n = a.Length; ` `        ``intialize(n); ` `        ``Console.WriteLine(solve(a, 0, n - 1)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output :

```2400
```

Time Complexity: O(n^3)
Auxiliary Space: O(n^2)