# How to perform Matrix Chain Multiplication

## Problem

We are given 'n' matrices, and we have to multiply them in such a way that the total number of operations is minimum.

## Solution

The matrix chain ordering problem, also known as matrix chain multiplication, is an optimization issue that asks what is the most effective way to multiply a given series of matrices. Choosing the order of the matrix multiplications involved is the challenge; doing the multiplications is not the problem. Dynamic programming may help to find a solution to the issue.

# Top-down Solution # C++ code

 // TOP DOWN APPROACH // BOARD INFINITY #includeusing namespace std;// Function to find the minimum number of Multiplication//  steps required in multiplying a chain of n matrices.int MatrixChainMultiplication(int mat[],int low, int high){    // If we are left with one matrix then     // we don't need any multiplication steps.    if(low==high)        return 0;        // Initializing minCost with very     // large value.    int minCost=INT_MAX;        // Iterating from low to high - 1    for(int k=low;k
write your code here: Coding Playground

Time Complexity: O(n^3)

Space Complexity: O(n^2)

# Bottom-up Solution # C++

 // BOTTOM UP APPROACH // BOARD INFINITY#includeusing namespace std;// Function to find the minimum number of Multiplication//  steps required in multiplying chain of n matrices.int MatrixChainMultiplication(int mat[],int n){    // Making 2d DP array of dimensions     // (n-1)*(n-1)    int dp[n-1][n-1];        // Iterating while gap between first     // length vary from 0 to n-1.    for(int gap=0;gap1, then we need to             // find the optimal method.             else{                // Initializing minCost with very large value.                int minCost=INT_MAX;                                // Iterating from k=i to                 // k = j-1 and finding cost.                /*                 Cost = Cost of Multiplying chain on left side +                        Cost of Multiplying chain on right side +                        Cost of Multiplying matrix obtained from left                         and right side.                */                for(int k=i;k
write your code here: Coding Playground

Time Complexity: O(n^3)

Space Complexity: O(n^2)

## Conclusion

• The bare minimum of multiplication operations necessary to multiply a chain of matrices has been determined in the matrix chain multiplication problem.
• Finding the bare minimum of steps needed can significantly speed up multiplication.
• The dynamic programming method requires additional space to determine the smallest number of steps needed to multiply a series of matrices.
• To complete the operation effectively, choosing the order of matrix multiplication is crucial.
• Therefore, it has been calculated how many multiplication steps are necessary to multiply a chain matrix of length n.
• Since it would take a very long time to exhaustively test every possibility, dynamic programming is utilized to find the same.