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;            // 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)