Matrix Chain Multiplication (MCM)

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide the optimal order (parenthesization) to perform the multiplications to minimize the total number of scalar multiplications.

Examples

Example 1

Dimensions Array (p): [40, 20, 30, 10, 30]
Matrices:
- A1 of size 40 x 20
- A2 of size 20 x 30
- A3 of size 30 x 10
- A4 of size 10 x 30
Output: 26000
Explanation: There are 4 matrices of dimensions 40 x 20, 20 x 30, 30 x 10, 10 x 30.
- The multiplication of A1 x (A2 x A3) x A4 requires:
  - A2 x A3 takes 20 x 30 x 10 = 6000 operations.
  - A1 x (A2 A3) takes 40 x 20 x 10 = 8000 operations.
  - (A1 (A2 A3)) x A4 takes 40 x 10 x 30 = 12000 operations.
  - Total: 6000 + 8000 + 12000 = 26000 operations.

Mathematical Substructure

Let dp[i][j] represent the minimum number of scalar multiplications needed to compute the matrix chain product A_i x A_{i+1} x ... x A_j.

For any split point k (where i <= k < j), we divide the chain into two subchains: A_i...A_k and A_{k+1}...A_j.

dp[i][j] = min( dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] ) for all i <= k < j

Base Case

dp[i][i] = 0 for all 1 <= i <= n (A single matrix requires 0 multiplications).

1. Recursive Solution (Naive)

This approach has an exponential time complexity of O(2^N).

function matrixChainRecursive(p, i, j) {
    if (i === j) return 0;
 
    let min = Infinity;
 
    // Place parenthesis at all possible positions between i and j
    for (let k = i; k < j; k++) {
        const count = matrixChainRecursive(p, i, k) +
                      matrixChainRecursive(p, k + 1, j) +
                      p[i - 1] * p[k] * p[j];
 
        if (count < min) {
            min = count;
        }
    }
 
    return min;
}

2. Memoization Solution (Top-Down DP)

function matrixChainMemoization(p) {
    const n = p.length;
    const memo = Array.from({ length: n }, () => new Array(n).fill(-1));
 
    function helper(i, j) {
        if (i === j) return 0;
 
        if (memo[i][j] !== -1) return memo[i][j];
 
        let min = Infinity;
 
        for (let k = i; k < j; k++) {
            const count = helper(i, k) +
                          helper(k + 1, j) +
                          p[i - 1] * p[k] * p[j];
 
            if (count < min) {
                min = count;
            }
        }
 
        memo[i][j] = min;
        return min;
    }
 
    return helper(1, n - 1);
}

3. Tabulation Solution (Bottom-Up DP)

We construct a 2D table dp of size n x n and fill it based on subchain length (gap L).

function matrixChainTabulation(p) {
    const n = p.length;
    // dp[i][j] is the minimum number of multiplications to compute matrix A_i...j
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
 
    // L is chain length. L = 1 means single matrix, which has 0 multiplications (already 0)
    for (let L = 2; L < n; L++) {
        for (let i = 1; i < n - L + 1; i++) {
            let j = i + L - 1;
            dp[i][j] = Infinity;
 
            for (let k = i; k < j; k++) {
                // q = cost/scalar multiplications
                const q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < dp[i][j]) {
                    dp[i][j] = q;
                }
            }
        }
    }
 
    return dp[1][n - 1];
}
 
// Driver code
const p = [40, 20, 30, 10, 30];
console.log("Minimum multiplications required:", matrixChainTabulation(p));
// Output: Minimum multiplications required: 26000

Complexity Analysis

Time Complexity: O(N^3)
- There are $N^2$ states in the DP table, and for each state, we iterate up to $N$ times to find the optimal split point $k$.
Space Complexity: O(N^2)
- To store the 2D DP table.

Subset Sum Problem Palindrome Partitioning