Matrix Chain Multiplication in DSA Typescript

Mental Model

We want to find the best way to multiply a chain of matrices so that the total number of multiplications is as small as possible.

Analogy: Imagine you have several boxes to stack, and the order you stack them affects how much effort it takes. Choosing the right order saves a lot of work.

Matrices: A1(10x30) -> A2(30x5) -> A3(5x60)
Goal: Find best order to multiply A1 x A2 x A3

Chain: [10, 30, 5, 60]
Each number is a dimension between matrices

Initial:
A1(10x30) -> A2(30x5) -> A3(5x60) -> null

Dry Run Walkthrough

Input: matrices dimensions: [10, 30, 5, 60]

Goal: Find the minimum number of scalar multiplications needed to multiply A1 x A2 x A3

Step 1: Calculate cost of multiplying A1 and A2 first

Cost = 10 x 30 x 5 = 1500 multiplications

Why: We try one way to parenthesize to see the cost

Step 2: Calculate cost of multiplying A2 and A3 first

Cost = 30 x 5 x 60 = 9000 multiplications

Why: Try the other way to parenthesize to compare costs

Step 3: Calculate total cost if multiply (A1xA2) then multiply result with A3

Total cost = 1500 + (10 x 5 x 60) = 1500 + 3000 = 4500

Why: After first multiplication, multiply the result with A3

Step 4: Calculate total cost if multiply A1 with (A2xA3)

Total cost = 9000 + (10 x 30 x 60) = 9000 + 18000 = 27000

Why: After second multiplication, multiply A1 with the result

Step 5: Compare both total costs and choose minimum

Minimum cost = 4500 multiplications by multiplying (A1xA2) first

Why: We want the least number of multiplications

Result:

Minimum multiplication cost = 4500

Annotated Code

DSA Typescript

class MatrixChainMultiplication {
  static matrixChainOrder(p: number[]): number {
    const n = p.length - 1;
    const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

    for (let L = 2; L <= n; L++) {
      for (let i = 0; i <= n - L; i++) {
        const j = i + L - 1;
        m[i][j] = Number.MAX_SAFE_INTEGER;
        for (let k = i; k < j; k++) {
          const cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
          if (cost < m[i][j]) {
            m[i][j] = cost;
          }
        }
      }
    }
    return m[0][n - 1];
  }
}

// Driver code
const dimensions = [10, 30, 5, 60];
const minCost = MatrixChainMultiplication.matrixChainOrder(dimensions);
console.log(minCost);

for (let L = 2; L <= n; L++) {

increase chain length from 2 to n

for (let i = 0; i <= n - L; i++) {

set start index of chain

const j = i + L - 1;

set end index of chain

m[i][j] = Number.MAX_SAFE_INTEGER;

initialize minimum cost for this chain segment

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

try all possible split points

const cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];

calculate cost of splitting at k

if (cost < m[i][j]) { m[i][j] = cost; }

update minimum cost if current split is cheaper

return m[0][n - 1];

return minimum cost for full chain

Output

4500

Complexity Analysis

Time: O(n^3) because we check all chain lengths, start points, and split points

Space: O(n^2) because we store minimum costs for all subchains in a 2D table

vs Alternative: Naive approach tries all parenthesizations recursively with exponential time; dynamic programming reduces it to polynomial time

Edge Cases

Only one matrix (e.g., [10, 20])

No multiplication needed, cost is zero

DSA Typescript

const n = p.length - 1;

Two matrices (e.g., [10, 20, 30])

Direct multiplication cost calculated without splits

DSA Typescript

for (let L = 2; L <= n; L++) {

Matrices with same dimensions (e.g., [10, 10, 10, 10])

Algorithm still finds minimum cost correctly

DSA Typescript

if (cost < m[i][j]) { m[i][j] = cost; }

When to Use This Pattern

When you see a problem asking for the best way to multiply a sequence of matrices with minimal cost, use the Matrix Chain Multiplication pattern because it optimizes the order of operations.

Common Mistakes

Mistake: Confusing matrix dimensions and using wrong indices for cost calculation
Fix: Use p[i] * p[k+1] * p[j+1] for cost calculation to match matrix dimensions correctly

Mistake: Not initializing the cost table properly leading to incorrect minimum cost
Fix: Initialize m[i][j] to a very large number before checking splits

Summary

Finds the minimum number of scalar multiplications needed to multiply a chain of matrices.

Use when you want to multiply multiple matrices efficiently by choosing the best order.

The key insight is that the problem can be broken into smaller subproblems and solved using dynamic programming.