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 solutionlong 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 numbersimport 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 npimport 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 ansdef 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 numbersusing 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 solutionvar 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
2400
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 codeint 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 ansdef 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 codea = [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 codeconst a = [40, 60, 20];const n = a.length;console.log(solve(a, n));//This code is contributed by chinmaya121221 |
Output
2400
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
