Matrix Chain Multiplication

Matrix multiplication is associative: (A·B)·C and A·(B·C) give the identical result. But the *amount of arithmetic* differs wildly depending on how you bracket the chain. Matrix chain multiplication finds the parenthesization that needs the fewest scalar multiplications. It's a classic *interval DP*: the answer for a stretch is built from the answers for its pieces.

Why bracketing matters

Multiplying a p×q matrix by a q×r matrix costs p·q·r scalar multiplications and yields a p×r matrix. So with A (10×100), B (100×5), C (5×50): (A·B)·C costs 10·100·5 + 10·5·50 = 5000 + 2500 = 7500, while A·(B·C) costs 100·5·50 + 10·100·50 = 25000 + 50000 = 75000 — ten times more for the same product.

The interval DP

Let m[i][j] = the fewest scalar multiplications to compute the product A_i · … · A_j. A single matrix costs nothing, so m[i][i] = 0. For a longer stretch, try every split point `k` between i and j: do the left half, do the right half, then multiply the two resulting matrices together.

1. 1Base case: m[i][i] = 0 — one matrix needs no multiplication.
2. 2For a stretch i..j, pick a split k (i ≤ k < j).
3. 3Cost of that split = m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j] (the two halves, plus combining them).
4. 4m[i][j] = the minimum of that cost over all k.
5. 5Solve by increasing chain length so every sub-stretch is ready before you need it.

function matrixChainOrder(p) {
  const n = p.length - 1;            // number of matrices
  const m = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
  for (let len = 2; len <= n; len++) {        // chain length
    for (let i = 1; i <= n - len + 1; i++) {
      const j = i + len - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (cost < m[i][j]) m[i][j] = cost;
      }
    }
  }
  return m[1][n];
}