jsschools

Matrix Chain Multiplication

Finds the optimal parenthesisation of a chain of matrices that minimises the total number of scalar multiplications, using interval DP.

Spec ↗

Syntax

matrixChain(dims)

Parameters

NameTypeRequiredDescription
dims number[] Yes Array of n+1 dimensions where the i-th matrix has dimensions dims[i-1] × dims[i]. Length must be ≥ 2.

Returns

number — Minimum number of scalar multiplications to compute the product of all matrices.

Examples

function matrixChain(dims) {
  const n = dims.length - 1; // number of matrices
  // dp[i][j] = min cost to multiply matrices i..j (0-indexed)
  const dp = Array.from({length: n}, () => new Array(n).fill(0));

  for (let len = 2; len <= n; len++) {         // chain length
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
        if (cost < dp[i][j]) dp[i][j] = cost;
      }
    }
  }
  return dp[0][n - 1];
}

// Matrices: 10×30, 30×5, 5×60 → min cost is (10×30×5) + (10×5×60) = 1500+3000 = 4500
console.log(matrixChain([10, 30, 5, 60]));
Output 
4500

// Track the split points to reconstruct the parenthesisation
function matrixChainSplit(dims) {
  const n = dims.length - 1;
  const dp = Array.from({length:n},()=>new Array(n).fill(0));
  const split = Array.from({length:n},()=>new Array(n).fill(0));

  for(let len=2;len<=n;len++)
    for(let i=0;i<=n-len;i++){
      const j=i+len-1; dp[i][j]=Infinity;
      for(let k=i;k<j;k++){
        const c=dp[i][k]+dp[k+1][j]+dims[i]*dims[k+1]*dims[j+1];
        if(c<dp[i][j]){dp[i][j]=c;split[i][j]=k;}
      }
    }

  function order(i, j) {
    if(i===j) return `A${i+1}`;
    return `(${order(i,split[i][j])}×${order(split[i][j]+1,j)})`;
  }
  return { cost: dp[0][n-1], order: order(0, n-1) };
}

console.log(matrixChainSplit([10, 30, 5, 60]));
Output 
{ cost: 4500, order: '(A1×(A2×A3))' }

Notes

| Case | Time | Space | |---------|--------|--------| | Best | O(n³) | O(n²) | | Average | O(n³) | O(n²) | | Worst | O(n³) | O(n²) | Matrix chain multiplication is a classic **interval DP** problem: the state dp[i][j] depends on dp[i][k] and dp[k+1][j] for all k in [i,j-1]. The order of evaluation goes from shorter chains to longer. Note this finds the optimal order for performing the multiplications; the actual matrix multiplication cost depends on the dimensions, not the values. This is commonly used in compiler optimisation and scientific computing libraries to plan efficient tensor contractions.

See also