Matrix Chain Multiplication (MCM)

Problem

Given an array arr[] which represents the dimensions of a sequence of matrices where the i^th matrix has the dimensions (arr[i-1] x arr[i]) for i>=1, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications. (link).

Find the minimum number of operations needed to multiply all the matrices.

Examples:

Input: arr[] = [2, 1, 3, 4]
Output: 20
Explanation: There are 3 matrices of dimensions 2 × 1, 1 × 3, and 3 × 4, Let this 3 input matrices be M1, M2, and M3. There are two ways to multiply: ((M1 x M2) x M3) and (M1 x (M2 x M3)), note that the result of (M1 x M2) is a 2 x 3 matrix and result of (M2 x M3) is a 1 x 4 matrix. 
((M1 x M2) x M3)  requires (2 x 1 x 3) + (2 x 3 x 4) = 30 
(M1 x (M2 x M3))  requires (1 x 3 x 4) + (2 x 1 x 4) = 20. 
The minimum of these two is 20.

Input: arr[] = [1, 2, 3, 4, 3]
Output: 30
Explanation: There are 4 matrices of dimensions 1 × 2, 2 × 3, 3 × 4, 4 × 3. Let this 4 input matrices be M1, M2, M3 and M4. The minimum number of multiplications are obtained by ((M1 x M2) x M3) x M4). The minimum number is (1 x 2 x 3) + (1 x 3 x 4) + (1 x 4 x 3) = 30.

Input: arr[] = [3, 4]
Output: 0
Explanation: As there is only one matrix so, there is no cost of multiplication.

Constraints:
2 ≤ arr.size() ≤ 100
1 ≤ arr[i] ≤ 200

Partition DP Pattern

Introduction

When there are multiple ways to solve a problem, we need to use the partition DP approach.

1 + 2 + 3 × 5

(1+2+3) x 5

(1+2) + (3 x5)

Partitioning can occur anywhere, so we should calculate all possible ways to get the minimum or maximum result.

MCM Basics

A (2x2) 
1 2
3 1

B (2x1)
2
3

A x B
=
1x2+2x3
3x2+1x3

=
8
9

Total mulitplications = 2 x 2 x 1 = 4

ABC 

A = 10 × 30

B = 30 × 5

C = 5 × 60

(AB)xC
Number of operations for AB (10,5) multiplication = 10 × 30 × 5 = 1500
Number of operations for (AB)xC (10,60) multiplication = 10 × 5 × 60 = 3000
total operations = 4500

Ax(BC)
Number of operations for BC (30,60) multiplication = 30 × 5 × 60 = 9000
Number of operations for Ax(BC) (10,60) multiplication = 10 × 30 × 60 = 18000
total operations = 27000

Minimum number of operations is 4500

Matrices dimensions

Given an arr[] = [10, 20, 30, 40, 50]

This resembles the dimensions of N-1 matrices. So total N-1 matrices.

A = 10 × 20

B = 20×30

C = 30×40

D = 40×50

Dimension of ith matrix = arr[i-1] x arr[i]

Partitioning DP Rules

Rule 1 : Start with entire block f(i, j) where i is the start point and j is the end point.

ABCD

(A) (BCD)
(AB) (CD)
(ABC) (D)

Rule 2: Try all partitions (Run a loop to try all partitions)

Rule 3: Return the best possible 2 partiions.

Example - ABCD

Fixed operations

We can easily calculate the operations of the 2 partitions without computing the each partitions operations because we know the resultant matrix dimensions

A (BCD)

Dimensions
A = 10 × 20

B = 20×30

C = 30×40

D = 40×50

BCD dimensions = 20 x 50

A BCD operations = 10 x 20 x 50

if we assume partition is at the kth index
Then our answer would be arr[i-1] x arr[k] x arr[j]

Solution

Recursion

Time - O(expotential)

Space - O(n)

class Solution {

    static int f(int i, int j, int[] arr){

        if(i==j) return 0;

        int ans = Integer.MAX_VALUE;

        for(int k=i; k<j; k++){

            /**
             * AK K+1B
             * (i-1, i) .... (k-1, k) - (k, k+1) ... (j-1, j)
             * (i-1, k) - (k, j)
             * Fixed operations i-1 x k x j
            */

            int fixedOperations = arr[i-1] * arr[k] * arr[j];
            int totalOperations = fixedOperations + f(i, k, arr) + f(k+1, j, arr);

            ans = Math.min(ans, totalOperations);
        }

        return ans;
    }

    static int matrixMultiplication(int arr[]) {


        return f(1, arr.length-1, arr);
    }
}

Memoization

Time - O(nxn) x O(n) → loop = O(n³)

Space - O(nxn) + O(n)

class Solution {

    static int f(int i, int j, int[] arr, int[][] dp){

        if(i==j) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int ans = Integer.MAX_VALUE;

        for(int k=i; k<j; k++){

            /**
             * AK K+1B
             * (i-1, i) x (k-1, k) - (k, k+1) x (j-1, j)
             * (i-1, k) - (k, j)
             * Fixed operations i-1 x k x j
            */

            int fixedOperations = arr[i-1] * arr[k] * arr[j];
            int totalOperations = fixedOperations + f(i, k, arr, dp) + f(k+1, j, arr, dp);

            ans = Math.min(ans, totalOperations);
        }

        return dp[i][j]=ans;
    }

    static int matrixMultiplication(int arr[]) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        for(int[] row : dp){
            Arrays.fill(row, -1);
        }

        return f(1, n-1, arr, dp);
    }
}

Tabulation

Base case i==j we need to put 0 in the dp but while initializationg itself the dp is initialized with all 0’s.

Time - O(n³)

Space - O(nxn)

class Solution {


    static int matrixMultiplication(int arr[]) {
        int n = arr.length;
        int[][] dp = new int[n][n];


        for(int i=n-1; i>=1; i--){
            for(int j=i+1; j<n; j++){
                int ans = Integer.MAX_VALUE;

                for(int k=i; k<j; k++){

                    /**
                     * AK K+1B
                     * (i-1, i) x (k-1, k) - (k, k+1) x (j-1, j)
                     * (i-1, k) - (k, j)
                     * Fixed operations i-1 x k x j
                    */

                    int fixedOperations = arr[i-1] * arr[k] * arr[j];
                    int totalOperations = fixedOperations 
                                        + dp[i][k] 
                                        + dp[k+1][j];

                    ans = Math.min(ans, totalOperations);
                }

                dp[i][j] = ans;
            }
        }

        return dp[1][n-1];
    }
}