Matrix Chain Multiplication

Time: O(n^3)

Space: O(n^2)

Intuition

dp[i][j] = minimum number of scalar multiplications to compute the product of matrices i through j. Split at every position k between i and j; the cost is dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j].

Algorithm

1dp[i][i]=0. Fill for increasing chain lengths.
2For l from 2 to n: for i from 1 to n-l+1: j=i+l-1. dp[i][j]=INF.
3For k from i to j-1: cost=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]. dp[i][j]=min.

Example Walkthrough

Input: p=[1,2,3,4] (3 matrices: 1Ã—2, 2Ã—3, 3Ã—4)

1.dp[1][2]=1*2*3=6. dp[2][3]=2*3*4=24. dp[1][3]=min(dp[1][1]+dp[2][3]+1*2*4, dp[1][2]+dp[3][3]+1*3*4)=min(0+24+8,6+0+12)=min(32,18)=18.

Output: 18

Common Pitfalls

•p[i] is the number of ROWS of matrix i and COLUMNS of matrix i-1. Use 1-indexed arrays carefully.

Matrix Chain Multiplication.java

Java

// Approach: DP on intervals. dp[i][j] = min scalar multiplications for matrices i to j.
// Split at every k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]).
// Time: O(n^3) Space: O(n^2)
class Solution {
    static int matrixMultiplication(int arr[]) {
        int n = arr.length;
        int[][] dp = new int[n + 1][n + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                dp[i][j] = -1;
        }

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

    public static int mcm(int[] arr, int i, int j, int[][] dp) {
        // base case
        if (i >= j)
            return 0;

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

        int mn = Integer.MAX_VALUE;
        for (int k = i; k <= j - 1; k++) { // ((A)(BCD) -> ((AB(CD))) -> ((ABC)(D))
            int temp = mcm(arr, i, k, dp) + mcm(arr, k + 1, j, dp) + arr[i - 1] * arr[k] * arr[j];
            mn = Math.min(mn, temp);
        }

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

Was this solution helpful?