Given the dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum.
Examples:
Input: arr[] = {40, 20, 30, 10, 30}
Output: 26000
Explanation:There are 4 matrices of dimensions 40×20, 20×30, 30×10, 10×30.
Let the input 4 matrices be A, B, C and D.
The minimum number of  multiplications are obtained byÂ
putting parenthesis in following way (A(BC))D.
The minimum is 20*30*10 + 40*20*10 + 40*10*30Input: arr[] = {1, 2, 3, 4, 3}
Output: 30
Explanation: There are 4 matrices of dimensions 1×2, 2×3, 3×4, 4×3.Â
Let the input 4 matrices be A, B, C and D. Â
The minimum number of multiplications are obtained byÂ
putting parenthesis in following way ((AB)C)D.
The minimum number is 1*2*3 + 1*3*4 + 1*4*3 = 30Input: arr[] = {10, 20, 30}
Output: 6000Â Â
Explanation: There are only two matrices of dimensions 10×20 and 20×30.Â
So there  is only one way to multiply the matrices, cost of which is 10*20*30
Matrix Chain Multiplication using Recursion:
We can solve the problem using recursion based on the following facts and observations:
Two matrices of size m*n and n*p when multiplied, they generate a matrix of size m*p and the number of multiplications performed are m*n*p.
Now, for a given chain of N matrices, the first partition can be done in N-1 ways. For example, sequence of matrices A, B, C and D can be grouped as (A)(BCD), (AB)(CD) or (ABC)(D) in these 3 ways.Â
So a range [i, j] can be broken into two groups like {[i, i+1], [i+1, j]}, {[i, i+2], [i+2, j]}, . . . , {[i, j-1], [j-1, j]}.
- Each of the groups can be further partitioned into smaller groups and we can find the total required multiplications by solving for each of the groups.
- The minimum number of multiplications among all the first partitions is the required answer.
Follow the steps mentioned below to implement the approach:
- Create a recursive function that takes i and j as parameters that determines the range of a group.
- Iterate from k = i to j to partition the given range into two groups.
- Call the recursive function for these groups.
- Return the minimum value among all the partitions as the required minimum number of multiplications to multiply all the matrices of this group.
- The minimum value returned for the range 0 to N-1 is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the // matrix chain multiplication using recursion Â
#include <bits/stdc++.h> using namespace std; Â
// Matrix Ai has dimension p[i-1] x p[i] // for i = 1 . . . n int MatrixChainOrder( int p[], int i, int j) { Â Â Â Â if (i == j) Â Â Â Â Â Â Â Â return 0; Â Â Â Â int k; Â Â Â Â int mini = INT_MAX; Â Â Â Â int count; Â
    // Place parenthesis at different places     // between first and last matrix,     // recursively calculate count of multiplications     // for each parenthesis placement     // and return the minimum count     for (k = i; k < j; k++)     {         count = MatrixChainOrder(p, i, k)                 + MatrixChainOrder(p, k + 1, j)                 + p[i - 1] * p[k] * p[j]; Â
        mini = min(count, mini);     } Â
    // Return minimum count     return mini; } Â
// Driver Code int main() { Â Â Â Â int arr[] = { 1, 2, 3, 4, 3 }; Â Â Â Â int N = sizeof (arr) / sizeof (arr[0]); Â
    // Function call     cout << "Minimum number of multiplications is "          << MatrixChainOrder(arr, 1, N - 1);     return 0; } Â
// This code is contributed by Shivi_Aggarwal |
C
// C code to implement the // matrix chain multiplication using recursion Â
#include <limits.h> #include <stdio.h> Â
// Matrix Ai has dimension p[i-1] x p[i] // for i = 1 . . . n int MatrixChainOrder( int p[], int i, int j) { Â Â Â Â if (i == j) Â Â Â Â Â Â Â Â return 0; Â Â Â Â int k; Â Â Â Â int min = INT_MAX; Â Â Â Â int count; Â
    // Place parenthesis at different places     // between first and last matrix,     // recursively calculate count of multiplications     // for each parenthesis placement     // and return the minimum count     for (k = i; k < j; k++)     {         count = MatrixChainOrder(p, i, k)                 + MatrixChainOrder(p, k + 1, j)                 + p[i - 1] * p[k] * p[j]; Â
        if (count < min)             min = count;     } Â
    // Return minimum count     return min; } Â
// Driver code int main() { Â Â Â Â int arr[] = { 1, 2, 3, 4, 3 }; Â Â Â Â int N = sizeof (arr) / sizeof (arr[0]); Â
    // Function call     printf ( "Minimum number of multiplications is %d " ,            MatrixChainOrder(arr, 1, N - 1));     getchar ();     return 0; } |
Java
// Java code to implement the // matrix chain multiplication using recursion import java.io.*; import java.util.*; class MatrixChainMultiplication { Â
    // Matrix Ai has dimension p[i-1] x p[i]     // for i = 1 . . . n     static int MatrixChainOrder( int p[], int i, int j)     {         if (i == j)             return 0 ; Â
        int min = Integer.MAX_VALUE; Â
        // Place parenthesis at different places         // between first and last matrix,         // recursively calculate count of multiplications         // for each parenthesis placement         // and return the minimum count         for ( int k = i; k < j; k++) {             int count = MatrixChainOrder(p, i, k)                         + MatrixChainOrder(p, k + 1 , j)                         + p[i - 1 ] * p[k] * p[j]; Â
            if (count < min)                 min = count;         } Â
        // Return minimum count         return min;     } Â
    // Driver code     public static void main(String args[])     {         int arr[] = new int [] { 1 , 2 , 3 , 4 , 3 };         int N = arr.length; Â
        // Function call         System.out.println(             "Minimum number of multiplications is "             + MatrixChainOrder(arr, 1 , N - 1 ));     } } /* This code is contributed by Rajat Mishra*/ |
Python3
# Python code to implement the # matrix chain multiplication using recursion Â
import sys Â
# Matrix A[i] has dimension p[i-1] x p[i] # for i = 1..n def MatrixChainOrder(p, i, j): Â Â Â Â if i = = j: Â Â Â Â Â Â Â Â return 0 Â
    _min = sys.maxsize Â
    # Place parenthesis at different places     # between first and last matrix,     # recursively calculate count of multiplications     # for each parenthesis placement     # and return the minimum count     for k in range (i, j): Â
        count = (MatrixChainOrder(p, i, k)                  + MatrixChainOrder(p, k + 1 , j)                  + p[i - 1 ] * p[k] * p[j]) Â
        if count < _min:             _min = count Â
    # Return minimum count     return _min Â
Â
# Driver code if __name__ = = '__main__' :     arr = [ 1 , 2 , 3 , 4 , 3 ]     N = len (arr)          # Function call     print ( "Minimum number of multiplications is " ,       MatrixChainOrder(arr, 1 , N - 1 )) Â
# This code is contributed by Aryan Garg |
C#
// C# code to implement the // matrix chain multiplication using recursion Â
using System; Â
class GFG { Â
    // Matrix Ai has dimension p[i-1] x p[i]     // for i = 1..n     static int MatrixChainOrder( int [] p, int i, int j)     { Â
        if (i == j)             return 0; Â
        int min = int .MaxValue; Â
        // Place parenthesis at different places         // between first and last matrix,         // recursively calculate count of multiplications         // for each parenthesis placement         // and return the minimum count         for ( int k = i; k < j; k++)         {             int count = MatrixChainOrder(p, i, k)                         + MatrixChainOrder(p, k + 1, j)                         + p[i - 1] * p[k] * p[j]; Â
            if (count < min)                 min = count;         } Â
        // Return minimum count         return min;     } Â
    // Driver code     public static void Main()     {         int [] arr = new int [] { 1, 2, 3, 4, 3 };         int N = arr.Length; Â
        // Function call         Console.Write(             "Minimum number of multiplications is "             + MatrixChainOrder(arr, 1, N - 1));     } } Â
// This code is contributed by Sam007. |
PHP
<?php // PHP code to implement the // matrix chain multiplication using recursion Â
// Matrix Ai has dimension // p[i-1] x p[i] for i = 1..n function MatrixChainOrder(& $p , $i , $j ) { Â Â Â Â if ( $i == $j ) Â Â Â Â Â Â Â Â return 0; Â Â Â Â $min = PHP_INT_MAX; Â
    // Place parenthesis at different places     // between first and last matrix,     // recursively calculate count of multiplications     // for each parenthesis placement     // and return the minimum count     for ( $k = $i ; $k < $j ; $k ++)     {         $count = MatrixChainOrder( $p , $i , $k ) +                  MatrixChainOrder( $p , $k + 1, $j ) +                                   $p [ $i - 1] *                                   $p [ $k ] * $p [ $j ]; Â
        if ( $count < $min )             $min = $count ;     } Â
    // Return minimum count     return $min ; } Â
// Driver Code $arr = array (1, 2, 3, 4, 3); $N = sizeof( $arr ); Â
echo "Minimum number of multiplications is " . Â Â Â Â Â Â MatrixChainOrder( $arr , 1, $N - 1); Â
// This code is contributed by ita_c ?> |
Javascript
<script> Â
// Javascript code to implement the // matrix chain multiplication using recursion Â
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n function MatrixChainOrder(p , i , j) { Â Â Â Â if (i == j) Â Â Â Â Â Â Â Â return 0; Â
    var min = Number.MAX_VALUE; Â
    // Place parenthesis at different places     // between first and last matrix,     // recursively calculate count of multiplications     // for each parenthesis placement     // and return the minimum count     var k=0;     for (k = i; k < j; k++)     {         var count = MatrixChainOrder(p, i, k)                     + MatrixChainOrder(p, k + 1, j)                     + p[i - 1] * p[k] * p[j]; Â
        if (count < min)             min = count;     } Â
    // Return minimum count     return min; } Â
// Driver code var arr = [ 1, 2, 3, 4, 3 ]; var N = arr.length; Â
document.write( Â Â Â Â "Minimum number of multiplications is " Â Â Â Â + MatrixChainOrder(arr, 1, N - 1)); Â
// This code contributed by shikhasingrajput Â
</script> |
Minimum number of multiplications is 30
The time complexity of the solution is exponential
Auxiliary Space: O(1)
Dynamic Programming Solution for Matrix Chain Multiplication using Memoization:
Below is the recursion tree for the 2nd example of the above recursive approach:
If observed carefully you can find the following two properties:
1) Optimal Substructure: In the above case, we are breaking the bigger groups into smaller subgroups and solving them to finally find the minimum number of multiplications. Therefore, it can be said that the problem has optimal substructure property.
2) Overlapping Subproblems:Â We can see in the recursion tree that the same subproblems are called again and again and this problem has the Overlapping Subproblems property.Â
So Matrix Chain Multiplication problem has both properties of a dynamic programming problem. So recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in a bottom up manner.
Follow the below steps to solve the problem:
- Build a matrix dp[][] of size N*N for memoization purposes.
- Use the same recursive call as done in the above approach:
- When we find a range (i, j) for which the value is already calculated, return the minimum value for that range (i.e., dp[i][j]).
- Otherwise, perform the recursive calls as mentioned earlier.
- The value stored at dp[0][N-1] is the required answer.
Below is the implementation of the above approachÂ
C++
// C++ program using memoization #include <bits/stdc++.h> using namespace std; int dp[100][100]; Â
// Function for matrix chain multiplication int matrixChainMemoised( int * p, int i, int j) { Â Â Â Â if (i == j) Â Â Â Â { Â Â Â Â Â Â Â Â return 0; Â Â Â Â } Â Â Â Â if (dp[i][j] != -1) Â Â Â Â { Â Â Â Â Â Â Â Â return dp[i][j]; Â Â Â Â } Â Â Â Â dp[i][j] = INT_MAX; Â Â Â Â for ( int k = i; k < j; k++) Â Â Â Â { Â Â Â Â Â Â Â Â dp[i][j] = min( Â Â Â Â Â Â Â Â Â Â Â Â dp[i][j], matrixChainMemoised(p, i, k) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â + matrixChainMemoised(p, k + 1, j) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â + p[i - 1] * p[k] * p[j]); Â Â Â Â } Â Â Â Â return dp[i][j]; } int MatrixChainOrder( int * p, int n) { Â Â Â Â int i = 1, j = n - 1; Â Â Â Â return matrixChainMemoised(p, i, j); } Â
// Driver Code int main() { Â Â Â Â int arr[] = { 1, 2, 3, 4 }; Â Â Â Â int n = sizeof (arr) / sizeof (arr[0]); Â Â Â Â memset (dp, -1, sizeof dp); Â
    cout << "Minimum number of multiplications is "          << MatrixChainOrder(arr, n); } Â
// This code is contributed by Sumit_Yadav |
Java
// Java program using memoization import java.io.*; import java.util.*; class GFG { Â
  static int [][] dp = new int [ 100 ][ 100 ]; Â
  // Function for matrix chain multiplication   static int matrixChainMemoised( int [] p, int i, int j)   {     if (i == j)     {       return 0 ;     }     if (dp[i][j] != - 1 )     {       return dp[i][j];     }     dp[i][j] = Integer.MAX_VALUE;     for ( int k = i; k < j; k++)     {       dp[i][j] = Math.min(         dp[i][j], matrixChainMemoised(p, i, k)         + matrixChainMemoised(p, k + 1 , j)         + p[i - 1 ] * p[k] * p[j]);     }     return dp[i][j];   } Â
  static int MatrixChainOrder( int [] p, int n)   {     int i = 1 , j = n - 1 ;     return matrixChainMemoised(p, i, j);   } Â
  // Driver Code   public static void main (String[] args)   { Â
    int arr[] = { 1 , 2 , 3 , 4 };     int n= arr.length; Â
    for ( int [] row : dp)       Arrays.fill(row, - 1 ); Â
    System.out.println( "Minimum number of multiplications is " + MatrixChainOrder(arr, n));   } } Â
// This code is contributed by avanitrachhadiya2155 |
Python3
# Python program using memoization import sys dp = [[ - 1 for i in range ( 100 )] for j in range ( 100 )] Â
# Function for matrix chain multiplication def matrixChainMemoised(p, i, j):     if (i = = j):         return 0          if (dp[i][j] ! = - 1 ):         return dp[i][j]          dp[i][j] = sys.maxsize          for k in range (i,j):         dp[i][j] = min (dp[i][j], matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1 , j) + p[i - 1 ] * p[k] * p[j])          return dp[i][j] Â
def MatrixChainOrder(p,n): Â Â Â Â i = 1 Â Â Â Â j = n - 1 Â Â Â Â Â Â Â return matrixChainMemoised(p, i, j) Â
# Driver Code arr = [ 1 , 2 , 3 , 4 ] n = len (arr) print ( "Minimum number of multiplications is" ,MatrixChainOrder(arr, n)) Â
# This code is contributed by rag2127 |
C#
// C# program using memoization using System; class GFG {          static int [,] dp = new int [100, 100];     // Function for matrix chain multiplication   static int matrixChainMemoised( int [] p, int i, int j)   {     if (i == j)     {       return 0;     }     if (dp[i, j] != -1)     {       return dp[i, j];     }     dp[i, j] = Int32.MaxValue;     for ( int k = i; k < j; k++)     {       dp[i, j] = Math.Min(         dp[i, j], matrixChainMemoised(p, i, k)         + matrixChainMemoised(p, k + 1, j)         + p[i - 1] * p[k] * p[j]);     }     return dp[i,j];   }     static int MatrixChainOrder( int [] p, int n)   {     int i = 1, j = n - 1;     return matrixChainMemoised(p, i, j);   }      // Driver code   static void Main()   {     int [] arr = { 1, 2, 3, 4 };     int n = arr.Length;          for ( int i = 0; i < 100; i++)     {         for ( int j = 0; j < 100; j++)         {             dp[i, j] = -1;         }     }       Console.WriteLine( "Minimum number of multiplications is " +                       MatrixChainOrder(arr, n));   } } Â
// This code is contributed by divyeshrabadiya07. |
Javascript
<script> Â
// Javascript program using memoization let dp = new Array(100); for ( var i = 0; i < dp.length; i++) { Â Â Â Â dp[i] = new Array(2); } Â
// Function for matrix chain multiplication function matrixChainMemoised(p, i, j) { Â Â Â Â if (i == j)Â Â Â Â Â { Â Â Â Â Â Â Â Â return 0; Â Â Â Â } Â Â Â Â if (dp[i][j] != -1)Â Â Â Â Â { Â Â Â Â Â Â Â Â return dp[i][j]; Â Â Â Â } Â Â Â Â Â Â Â Â Â dp[i][j] = Number.MAX_VALUE; Â Â Â Â for (let k = i; k < j; k++)Â Â Â Â Â { Â Â Â Â Â Â Â Â dp[i][j] = Math.min( Â Â Â Â Â Â Â Â Â Â Â Â dp[i][j], matrixChainMemoised(p, i, k) + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â matrixChainMemoised(p, k + 1, j) + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â p[i - 1] * p[k] * p[j]); Â Â Â Â } Â Â Â Â return dp[i][j]; } Â
function MatrixChainOrder(p, n) { Â Â Â Â let i = 1, j = n - 1; Â Â Â Â return matrixChainMemoised(p, i, j); } Â
// Driver code let arr = [ 1, 2, 3, 4 ]; let n = arr.length; Â
for ( var i = 0; i < dp.length; i++) { Â Â Â Â for ( var j = 0; j < dp.length; j++) Â Â Â Â { Â Â Â Â Â Â Â Â dp[i][j] = -1; Â Â Â Â } } Â
document.write( "Minimum number of multiplications is " + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â MatrixChainOrder(arr, n)); Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â // This code is contributed by target_2 Â
</script> |
Minimum number of multiplications is 18
Time Complexity: O(N3Â )
Auxiliary Space: O(N2) ignoring recursion stack space
Dynamic Programming Solution for Matrix Chain Multiplication using Tabulation (Iterative Approach):
In iterative approach, we initially need to find the number of multiplications required to multiply two adjacent matrices. We can use these values to find the minimum multiplication required for matrices in a range of length 3 and further use those values for ranges with higher lengths.Â
Build on the answer in this manner till the range becomes [0, N-1].
Follow the steps mentioned below to implement the idea:
- Iterate from l = 2 to N-1 which denotes the length of the range:
- Iterate from i = 0 to N-1:
- Find the right end of the range (j) having l matrices.
- Iterate from k = i+1 to j which denotes the point of partition.
- Multiply the matrices in range (i, k) and (k, j).
- This will create two matrices with dimensions arr[i-1]*arr[k] and arr[k]*arr[j].
- The number of multiplications to be performed to multiply these two matrices (say X) are arr[i-1]*arr[k]*arr[j].
- The total number of multiplications is dp[i][k]+ dp[k+1][j] + X.
- Iterate from i = 0 to N-1:
- The value stored at dp[1][N-1] is the required answer.
Below is the implementation of the above approach.
C++
// See the Cormen book for details of the // following algorithm #include <bits/stdc++.h> using namespace std; Â
// Matrix Ai has dimension p[i-1] x p[i] // for i = 1..n int MatrixChainOrder( int p[], int n) { Â
    /* For simplicity of the program, one     extra row and one extra column are     allocated in m[][]. 0th row and 0th     column of m[][] are not used */     int m[n][n]; Â
    int i, j, k, L, q; Â
    /* m[i, j] = Minimum number of scalar     multiplications needed to compute the     matrix A[i]A[i+1]...A[j] = A[i..j] where     dimension of A[i] is p[i-1] x p[i] */ Â
    // cost is zero when multiplying     // one matrix.     for (i = 1; i < n; i++)         m[i][i] = 0; Â
    // L is chain length.     for (L = 2; L < n; L++)     {         for (i = 1; i < n - L + 1; i++)         {             j = i + L - 1;             m[i][j] = INT_MAX;             for (k = i; k <= j - 1; k++)             {                 // q = cost/scalar multiplications                 q = m[i][k] + m[k + 1][j]                     + p[i - 1] * p[k] * p[j];                 if (q < m[i][j])                     m[i][j] = q;             }         }     } Â
    return m[1][n - 1]; } Â
// Driver Code int main() { Â Â Â Â int arr[] = { 1, 2, 3, 4 }; Â Â Â Â int size = sizeof (arr) / sizeof (arr[0]); Â
    cout << "Minimum number of multiplications is "          << MatrixChainOrder(arr, size); Â
    getchar ();     return 0; } Â
// This code is contributed // by Akanksha Rai |
C
// See the Cormen book for details of the following // algorithm #include <limits.h> #include <stdio.h> Â
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n int MatrixChainOrder( int p[], int n) { Â
    /* For simplicity of the program,        one extra row and one        extra column are allocated in m[][].        0th row and 0th        column of m[][] are not used */     int m[n][n]; Â
    int i, j, k, L, q; Â
    /* m[i, j] = Minimum number of        scalar multiplications        needed to compute the matrix        A[i]A[i+1]...A[j] =        A[i..j] where dimension of A[i]        is p[i-1] x p[i] */ Â
    // cost is zero when multiplying one matrix.     for (i = 1; i < n; i++)         m[i][i] = 0; Â
    // L is chain length.     for (L = 2; L < n; L++) {         for (i = 1; i < n - L + 1; i++)         {             j = i + L - 1;             m[i][j] = INT_MAX;             for (k = i; k <= j - 1; k++)             {                 // q = cost/scalar multiplications                 q = m[i][k] + m[k + 1][j]                     + p[i - 1] * p[k] * p[j];                 if (q < m[i][j])                     m[i][j] = q;             }         }     } Â
    return m[1][n - 1]; } Â
// Driver code int main() {     int arr[] = { 1, 2, 3, 4 };     int size = sizeof (arr) / sizeof (arr[0]); Â
    printf ( "Minimum number of multiplications is %d " ,            MatrixChainOrder(arr, size)); Â
    getchar ();     return 0; } |
Java
// Dynamic Programming Java implementation of Matrix // Chain Multiplication. // See the Cormen book for details of the following // algorithm import java.util.*; import java.io.*; class MatrixChainMultiplication { Â
    // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n     static int MatrixChainOrder( int p[], int n)     {         /* For simplicity of the         program, one extra row and         one extra column are allocated in m[][]. 0th row         and 0th column of m[][] are not used */         int m[][] = new int [n][n]; Â
        int i, j, k, L, q; Â
        /* m[i, j] = Minimum number of scalar         multiplications needed to compute the matrix         A[i]A[i+1]...A[j] = A[i..j] where         dimension of A[i] is p[i-1] x p[i] */ Â
        // cost is zero when multiplying one matrix.         for (i = 1 ; i < n; i++)             m[i][i] = 0 ; Â
        // L is chain length.         for (L = 2 ; L < n; L++)         {             for (i = 1 ; i < n - L + 1 ; i++)             {                 j = i + L - 1 ;                 if (j == n)                     continue ;                 m[i][j] = Integer.MAX_VALUE;                 for (k = i; k <= j - 1 ; k++)                 {                     // q = cost/scalar multiplications                     q = m[i][k] + m[k + 1 ][j]                         + p[i - 1 ] * p[k] * p[j];                     if (q < m[i][j])                         m[i][j] = q;                 }             }         } Â
        return m[ 1 ][n - 1 ];     } Â
    // Driver code     public static void main(String args[])     {         int arr[] = new int [] { 1 , 2 , 3 , 4 };         int size = arr.length; Â
        System.out.println(             "Minimum number of multiplications is "             + MatrixChainOrder(arr, size));     } } /* This code is contributed by Rajat Mishra*/ |
Python3
# Dynamic Programming Python implementation of Matrix # Chain Multiplication. See the Cormen book for details # of the following algorithm import sys maxint = int ( 1e9 + 7 ) # Matrix Ai has dimension p[i-1] x p[i] for i = 1..n Â
Â
def MatrixChainOrder(p, n):     # For simplicity of the program,     # one extra row and one     # extra column are allocated in m[][].     # 0th row and 0th     # column of m[][] are not used     m = [[ 0 for x in range (n)] for x in range (n)] Â
    # m[i, j] = Minimum number of scalar     # multiplications needed     # to compute the matrix A[i]A[i + 1]...A[j] =     # A[i..j] where     # dimension of A[i] is p[i-1] x p[i] Â
    # cost is zero when multiplying one matrix.     for i in range ( 1 , n):         m[i][i] = 0 Â
    # L is chain length.     for L in range ( 2 , n):         for i in range ( 1 , n - L + 1 ):             j = i + L - 1             m[i][j] = maxint             for k in range (i, j): Â
                # q = cost / scalar multiplications                 q = m[i][k] + m[k + 1 ][j] + p[i - 1 ] * p[k] * p[j]                 if q < m[i][j]:                     m[i][j] = q Â
    return m[ 1 ][n - 1 ] Â
Â
# Driver code arr = [ 1 , 2 , 3 , 4 ] size = len (arr) Â
print ( "Minimum number of multiplications is " + Â Â Â Â Â Â str (MatrixChainOrder(arr, size))) # This Code is contributed by Bhavya Jain |
C#
// Dynamic Programming C# implementation of // Matrix Chain Multiplication. // See the Cormen book for details of the // following algorithm using System; Â
class GFG { Â
    // Matrix Ai has dimension p[i-1] x p[i]     // for i = 1..n     static int MatrixChainOrder( int [] p, int n)     { Â
        /* For simplicity of the program, one         extra row and one extra column are         allocated in m[][]. 0th row and 0th         column of m[][] are not used */         int [, ] m = new int [n, n]; Â
        int i, j, k, L, q; Â
        /* m[i, j] = Minimum number of scalar         multiplications needed         to compute the matrix A[i]A[i+1]...A[j]         = A[i..j] where dimension of A[i] is         p[i-1] x p[i] */ Â
        // cost is zero when multiplying         // one matrix.         for (i = 1; i < n; i++)             m[i, i] = 0; Â
        // L is chain length.         for (L = 2; L < n; L++)         {             for (i = 1; i < n - L + 1; i++)             {                 j = i + L - 1;                 if (j == n)                     continue ;                 m[i, j] = int .MaxValue;                 for (k = i; k <= j - 1; k++)                 {                     // q = cost/scalar multiplications                     q = m[i, k] + m[k + 1, j]                         + p[i - 1] * p[k] * p[j];                     if (q < m[i, j])                         m[i, j] = q;                 }             }         } Â
        return m[1, n - 1];     } Â
    // Driver code     public static void Main()     {         int [] arr = new int [] { 1, 2, 3, 4 };         int size = arr.Length; Â
        Console.Write( "Minimum number of "                       + "multiplications is "                       + MatrixChainOrder(arr, size));     } } Â
// This code is contributed by Sam007 |
PHP
<?php // Dynamic Programming Python implementation // of Matrix Chain Multiplication. Â
// See the Cormen book for details of the // following algorithm Matrix Ai has // dimension p[i-1] x p[i] for i = 1..n function MatrixChainOrder( $p , $n ) {     /* For simplicity of the program, one     extra row and one extra column are     allocated in m[][]. 0th row and 0th     column of m[][] are not used */     $m [][] = array ( $n , $n ); Â
    /* m[i, j] = Minimum number of scalar     multiplications needed to compute the     matrix A[i]A[i+1]...A[j] = A[i..j] where     dimension of A[i] is p[i-1] x p[i] */ Â
    // cost is zero when multiplying one matrix.     for ( $i = 1; $i < $n ; $i ++)         $m [ $i ][ $i ] = 0; Â
    // L is chain length.     for ( $L = 2; $L < $n ; $L ++)     {         for ( $i = 1; $i < $n - $L + 1; $i ++)         {             $j = $i + $L - 1;             if ( $j == $n )                 continue ;             $m [ $i ][ $j ] = PHP_INT_MAX;             for ( $k = $i ; $k <= $j - 1; $k ++)             {                 // q = cost/scalar multiplications                 $q = $m [ $i ][ $k ] + $m [ $k + 1][ $j ] +                      $p [ $i - 1] * $p [ $k ] * $p [ $j ];                 if ( $q < $m [ $i ][ $j ])                     $m [ $i ][ $j ] = $q ;             }         }     } Â
    return $m [1][ $n -1]; } Â
// Driver Code $arr = array (1, 2, 3, 4); $size = sizeof( $arr ); Â
echo "Minimum number of multiplications is " . Â Â Â Â Â Â Â Â Â Â Â Â Â Â MatrixChainOrder( $arr , $size ); Â
// This code is contributed by Mukul Singh ?> |
Javascript
<script> Â
// Dynamic Programming javascript implementation of Matrix // Chain Multiplication. // See the Cormen book for details of the following // algorithm Â
Â
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n function MatrixChainOrder(p , n) {     /* For simplicity of the     program, one extra row and     one extra column are allocated in m. 0th row     and 0th column of m are not used */     var m = Array(n).fill(0).map(x => Array(n).fill(0)); Â
    var i, j, k, L, q; Â
    /* m[i, j] = Minimum number of scalar     multiplications needed to compute the matrix     A[i]A[i+1]...A[j] = A[i..j] where     dimension of A[i] is p[i-1] x p[i] */ Â
    // cost is zero when multiplying one matrix.     for (i = 1; i < n; i++)         m[i][i] = 0; Â
    // L is chain length.     for (L = 2; L < n; L++)     {         for (i = 1; i < n - L + 1; i++)         {             j = i + L - 1;             if (j == n)                 continue ;             m[i][j] = Number.MAX_VALUE;             for (k = i; k <= j - 1; k++)             {                 // q = cost/scalar multiplications                 q = m[i][k] + m[k + 1][j]                     + p[i - 1] * p[k] * p[j];                 if (q < m[i][j])                     m[i][j] = q;             }         }     } Â
    return m[1][n - 1]; } Â
// Driver code var arr = [ 1, 2, 3, 4 ]; var size = arr.length; Â
document.write( Â Â Â Â "Minimum number of multiplications is " Â Â Â Â + MatrixChainOrder(arr, size)); Â
// This code contributed by Princi Singh Â
</script> |
Minimum number of multiplications is 18
Time Complexity: O(N3Â )
Auxiliary Space: O(N2)
Matrix Chain Multiplication (A O(N^2) Solution)Â
Printing brackets in Matrix Chain Multiplication Problem
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Applications:Â
Minimum and Maximum values of an expression with * and +
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
[…] approach is similar to that of Matrix Chain Multiplication […]
[…] Â Â Â Â // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). […]