Tutorialspoint.dev

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 



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 <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 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[0]);
    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

<?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 intialize( $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);
intialize($n);
echo solve($a, 0, $n - 1) ;
  
// This code is contributed by anuj_67.
?>


Output :

2400

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter