Minimum sum of multiplications of n numbers

0 0 11 minutes read

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

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 DP_i,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.

DP_i,j = min(DP_i,j , (DP_i,k+DP_k+1,j+(cumulative_sum_i,k*cumulative_sum_k+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 <bits/stdc++.h>
using namespace std;
 
// Used in recursive 
// memoized solution
long long dp[1000][1000];
 
// 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 initialize(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[0]);
    initialize(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 initialize(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;
        initialize(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 initialize(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) 
    initialize(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 initialize(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;
        initialize(n);
        Console.WriteLine(solve(a, 0, n - 1));
         
    }
}
 
// This code is contributed by vt_m.

Javascript

<script>
 
// JavaScript program to find the 
// minimum sum of multiplication
// of n numbers
 
// Used in recursive 
// memoized solution
var dp = Array.from(Array(1000), ()=>Array(1000));
 
// function to calculate the cumulative 
// sum from a[i] to a[j]
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)
{
    // 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] = 1000000000;
     
    // we break them into k partitions 
    for (var 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];
}
 
function initialize(n)
{
    for (var i = 0; i <= n; i++) 
        for (var j = 0; j <= n; j++)
            dp[i][j] = -1;     
}
 
// Driver code 
var a = [40, 60, 20]; 
var n = a.length;
initialize(n);
document.write( solve(a, 0, n - 1));
 
</script>

PHP

<?php
// PHP program to find the 
// minimum sum of multiplication 
// of n numbers
 
 
// Used in recursive
// memoized solution
$dp = array(array());
 
// function to calculate the 
// cumulative sum from a[i] to a[j]
function sum( $a, $i, $j)
{ 
    $ans = 0;
    for ( $m = $i; $m <= $j; $m++) 
        $ans = ($ans + $a[$m]) % 100;
    return $ans;
}
 
function solve( $a, $i, $j)
{
    global $dp;
    // 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] = PHP_INT_MAX;
     
    // we break them into
    // k partitions 
    for ( $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];
}
 
function initialize( $n)
{
    global $dp;
    for ( $i = 0; $i <= $n; $i++) 
        for ( $j = 0; $j <= $n; $j++)
            $dp[$i][$j] = -1; 
}
 
// Driver code 
$a = array(40, 60, 20); 
$n = count($a);
initialize($n);
echo solve($a, 0, $n - 1) ;
 
// This code is contributed by anuj_67.
?>

Output

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

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a DP of size N*N to store the computations of subproblems.
Initialize Dp with 0.
Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
Return the final solution stored in dp[0][n-1].

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
// 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 n)
{
    long long dp[n][n];
 
    // Initializing the dp array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    }
 
    // Filling the dp array using tabulation
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
 
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], (dp[i][k] +
                                          dp[k + 1][j] +
                                          (sum(a, i, k) * sum(a, k + 1, j))));
            }
        }
    }
 
    // Return the minimum sum
    return dp[0][n - 1];
}
 
// Driver code
int main()
{
    int a[] = { 40, 60, 20 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << solve(a, n) << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class GFG {
 
    // Function to calculate the cumulative sum from a[i] to a[j]
    public 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;
    }
 
    public static long solve(int[] a, int n) {
        long[][] dp = new long[n][n];
 
        // Initializing the dp array
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 0);
        }
 
        // Filling the dp array using tabulation
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
 
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], (dp[i][k] +
                            dp[k + 1][j] +
                            (sum(a, i, k) * sum(a, k + 1, j))));
                }
            }
        }
 
        // Return the minimum sum
        return dp[0][n - 1];
    }
 
    // Driver code
    public static void main(String[] args) {
        int[] a = { 40, 60, 20 };
        int n = a.length;
 
        System.out.println(solve(a, n));
    }
}

Python3

def sum_arr(a, i, j):
    """
    Function to calculate the cumulative sum from a[i] to a[j]
    """
    ans = 0
    for m in range(i, j+1):
        ans = (ans + a[m]) % 100
    return ans
 
 
def solve(a, n):
    """
    Function to find the minimum sum required to 
    multiply matrices in a given order
    """
    # Initializing the dp array
    dp = [[0] * n for _ in range(n)]
 
    # Filling the dp array using tabulation
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Initialize the current cell with infinity to find the minimum sum later
            dp[i][j] = float('inf')  
 
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], (dp[i][k] +
                                          dp[k + 1][j] +
                                          (sum_arr(a, i, k) * sum_arr(a, k + 1, j))))
                # Compute the cost of multiplying matrices from i to k and k+1 to j
                # Update the minimum sum if a lower cost is found
 
    # Return the minimum sum
    return dp[0][n - 1]
 
 
# Driver code
a = [40, 60, 20]
n = len(a)
 
print(solve(a, n))

C#

using System;
 
namespace CumulativeSumExample {
class Program {
    // 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 n)
    {
        long[, ] dp = new long[n, n];
 
        // Initializing the dp array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = 0;
            }
        }
 
        // Filling the dp array using tabulation
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i, j] = int.MaxValue;
 
                for (int k = i; k < j; k++) {
                    dp[i, j] = Math.Min(
                        dp[i, j], (dp[i, k] + dp[k + 1, j]
                                   + (Sum(a, i, k)
                                      * Sum(a, k + 1, j))));
                }
            }
        }
 
        // Return the minimum sum
        return dp[0, n - 1];
    }
 
    // Driver code
    static void Main(string[] args)
    {
        int[] a = { 40, 60, 20 };
        int n = a.Length;
 
        Console.WriteLine(Solve(a, n));
    }
}
}

Javascript

function sum(a, i, j) {
    let ans = 0;
    for (let m = i; m <= j; m++) {
        ans = (ans + a[m]) % 100;
    }
    return ans;
}
 
function solve(a, n) {
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
 
    // Filling the dp array using tabulation
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i < n - len + 1; i++) {
            const j = i + len - 1;
            dp[i][j] = Number.MAX_VALUE;
 
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(
                    dp[i][j],
                    dp[i][k] + dp[k + 1][j] + sum(a, i, k) * sum(a, k + 1, j)
                );
            }
        }
    }
 
    // Return the minimum sum
    return dp[0][n - 1];
}
 
// Driver code
const a = [40, 60, 20];
const n = a.length;
 
console.log(solve(a, n));
//This code is contributed by chinmaya121221

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!