Skip to main content

Matrix Chain Multiplication

Problem​

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications.

The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices + 1) where the ith matrix has the dimensions (arr[i-1] x arr[i]).

Solution Approach​

Expected Time complexity: O(n3)O(n^3)

Click - to see solution code
class Solution {
   public:
    int matrixMultiplication(int N, int A[]) {
        int dp[200][200] = {0};
        memset(dp, 0, sizeof dp);
        int n = N - 1;
        for (int i = 1; i < n; i++) {
            int r = 0, c = i;
            while (c < n) {
                int val = INT_MAX;
                for (int pivot = r; pivot < c; pivot++) {
                    val = min(val, dp[r][pivot] + dp[pivot + 1][c] +
                                       A[r] * A[pivot + 1] * A[c + 1]);
                }
                dp[r][c] = val;
                r++;
                c++;
            }
        }
        return dp[0][n - 1];
    }
};