Matrix Chain Multiplication in DSA Typescript - Execution Trace

Concept Flow - Matrix Chain Multiplication

Start with matrices dimensions

↓

Initialize DP table with zeros on diagonal

↓

For chain length = 2 to n

↓

For each start index i

↓

For each split point k between i and j

↓

Calculate cost = cost_left + cost_right + multiplication cost

↓

Update DP[i

↓

Repeat until full chain cost computed

↓

Result in DP[0

The flow shows how we fill a table step-by-step to find the cheapest way to multiply a chain of matrices.

Execution Sample

DSA Typescript

const dims = [10, 20, 30, 40];
const n = dims.length - 1;
const dp = Array(n).fill(0).map(() => Array(n).fill(0));
for (let length = 2; length <= n; length++) {
  for (let i = 0; i <= n - length; i++) {
    let j = i + length - 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;
    }
  }
}

This code calculates the minimum multiplication cost for matrices with given dimensions.

Execution Table

Step	Operation	Indices (i,j)	Split k	Cost Calculated	DP Table State	Minimum Cost at DP[i][j]
1	Initialize diagonal	0,0	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
2	Initialize diagonal	1,1	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
3	Initialize diagonal	2,2	-	-	[[0, -, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	0
4	Calculate cost for length=2	0,1	0	10*20*30=6000	[[0, 6000, -, -], [-, 0, -, -], [-, -, 0, -], [-, -, -, 0]]	6000
5	Calculate cost for length=2	1,2	1	20*30*40=24000	[[0, 6000, -, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	24000
6	Calculate cost for length=3	0,2	0	dp[0][0]+dp[1][2]+10*20*40=0+24000+8000=32000	[[0, 6000, 32000, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	32000
7	Calculate cost for length=3	0,2	1	dp[0][1]+dp[2][2]+10*30*40=6000+0+12000=18000	[[0, 6000, 18000, -], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	18000
8	Calculate cost for length=4	0,3	0	dp[0][0]+dp[1][3]+10*20*40=0+Infinity+8000=Infinity	[[0, 6000, 18000, Infinity], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	Infinity
9	Calculate cost for length=4	0,3	1	dp[0][1]+dp[2][3]+6000+12000=6000+Infinity+12000=Infinity	[[0, 6000, 18000, Infinity], [-, 0, 24000, Infinity], [-, -, 0, -], [-, -, -, 0]]	Infinity
10	Calculate cost for length=4	0,3	2	dp[0][2]+dp[3][3]+18000+48000=18000+0+48000=66000	[[0, 6000, 18000, 66000], [-, 0, 24000, Infinity], [-, -, 0, -], [-, -, -, 0]]	66000
11	Calculate cost for length=4	1,3	1	dp[1][1]+dp[2][3]+0+12000=0+Infinity+12000=Infinity	[[0, 6000, 18000, 66000], [-, 0, 24000, -], [-, -, 0, -], [-, -, -, 0]]	Infinity
12	Calculate cost for length=4	1,3	2	dp[1][2]+dp[3][3]+24000+48000=24000+0+48000=72000	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, -], [-, -, -, 0]]	72000
13	Calculate cost for length=4	2,3	2	dp[2][2]+dp[3][3]+30*40*?=0+0+?	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, 1200], [-, -, -, 0]]	1200
14	Final result	0,3	-	-	[[0, 6000, 18000, 66000], [-, 0, 24000, 72000], [-, -, 0, 1200], [-, -, -, 0]]	66000

💡 All subproblems computed; minimum multiplication cost is dp[0][n-1] = 66000

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 10	After Step 12	Final
dp[0][0]	0	0	0	0	0	0	0
dp[1][1]	0	0	0	0	0	0	0
dp[2][2]	0	0	0	0	0	0	0
dp[3][3]	0	0	0	0	0	0	0
dp[0][1]	Infinity	6000	6000	6000	6000	6000	6000
dp[1][2]	Infinity	Infinity	24000	24000	24000	24000	24000
dp[0][2]	Infinity	Infinity	Infinity	18000	18000	18000	18000
dp[0][3]	Infinity	Infinity	Infinity	Infinity	66000	66000	66000
dp[1][3]	Infinity	Infinity	Infinity	Infinity	Infinity	72000	72000
dp[2][3]	Infinity	Infinity	Infinity	Infinity	Infinity	Infinity	1200

Key Moments - 3 Insights

Why do we initialize the diagonal of the DP table with zeros?

Because multiplying one matrix alone costs nothing, so dp[i][i] = 0 as shown in steps 1-3 of the execution_table.

Why do we try all split points k between i and j?

Because the chain can be split in different ways, and we want the minimum cost. The execution_table rows 6-7 show different k values and costs compared.

Why does the cost formula include dims[i]*dims[k+1]*dims[j+1]?

This represents the cost of multiplying two matrices after splitting at k. It matches the multiplication dimension rule and is used in cost calculations in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What is the minimum cost stored at dp[0][2] after considering split k=1?

A 32000

B 18000

C 6000

D 24000

💡 Hint

Check the 'Minimum Cost at DP[i][j]' column in row 7 of the execution_table.

At which step does the DP table first get a value for dp[0][1]?

A Step 4

B Step 6

C Step 2

D Step 10

💡 Hint

Look for when dp[0][1] changes from '-' or Infinity to a number in the execution_table.

If the dimension array dims changed to [10, 20, 10, 40], how would the cost at step 7 change?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Look at the cost formula in step 7 and consider how dims[k+1] affects multiplication cost.

Concept Snapshot

Matrix Chain Multiplication:
- Goal: Minimize scalar multiplications for matrix chain
- Use DP table dp[i][j] for min cost multiplying matrices i to j
- dp[i][i] = 0 (single matrix)
- For length 2 to n, compute dp[i][j] by trying all splits k
- Cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
- Result in dp[0][n-1]

Full Transcript

Matrix Chain Multiplication finds the cheapest way to multiply a sequence of matrices. We use a table dp where dp[i][j] stores the minimum cost to multiply matrices from i to j. The diagonal dp[i][i] is zero because one matrix alone needs no multiplication. We fill the table by increasing chain length, trying all split points k between i and j. For each split, we calculate cost as sum of left and right parts plus multiplication cost of resulting matrices. We keep the minimum cost in dp[i][j]. After filling the table, dp[0][n-1] gives the minimum multiplication cost for the full chain. The execution table shows step-by-step how costs are computed and updated. Key points include initializing the diagonal, trying all splits, and using the dimension array to calculate multiplication cost.

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

A. To find the maximum number of matrices that can be multiplied

B. To multiply all matrices in the chain directly without optimization

C. To count the total number of matrices in the chain

D. To find the minimum number of scalar multiplications needed to multiply a chain of matrices

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices to minimize cost.

2. Step 2: Identify what is minimized

   The cost minimized is the number of scalar multiplications, not the number of matrices or direct multiplication.

3. Final Answer:

   To find the minimum number of scalar multiplications needed to multiply a chain of matrices -> Option D

4. Quick Check:

   Goal = minimum scalar multiplications [OK]

Hint: Remember: minimize multiplication cost, not count matrices [OK]

Common Mistakes:

• Confusing multiplication count with matrix count
• Thinking the problem multiplies matrices directly
• Assuming maximum matrices multiplication is the goal

2. Which of the following is the correct TypeScript function signature for a recursive Matrix Chain Multiplication function that takes an array of matrix dimensions?

easy

A. function matrixChainOrder(dimensions: string): number

B. function matrixChainOrder(dimensions: number): number[]

C. function matrixChainOrder(dimensions: number[]): number

D. function matrixChainOrder(dimensions: number[][]): void

Solution

1. Step 1: Identify input type for matrix dimensions

   Matrix dimensions are given as an array of numbers representing sizes, so number[] is correct.

2. Step 2: Identify return type for minimum cost

   The function returns the minimum number of scalar multiplications, which is a number.

3. Final Answer:

   function matrixChainOrder(dimensions: number[]): number -> Option C

4. Quick Check:

   Input = number[], Output = number [OK]

Hint: Input is array of numbers, output is a single number [OK]

Common Mistakes:

• Using string instead of number array for dimensions
• Returning an array instead of a number
• Using 2D array or void return incorrectly

3. What is the output of the following TypeScript code snippet?

function 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 + 1; i++) {
      const j = i + L - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

console.log(matrixChainOrder([10, 20, 30, 40]));

medium

A. 18000

B. 24000

C. 30000

D. 60000

Solution

1. Step 1: Understand the input and matrix dimensions

   The input array [10, 20, 30, 40] represents matrices of dimensions 10x20, 20x30, and 30x40.

2. Step 2: Calculate minimum multiplication cost

   Possible parenthesizations:
   - (A1 x (A2 x A3)) = 20*30*40 + 10*20*40 = 24000 + 8000 = 32000
   - ((A1 x A2) x A3) = 10*20*30 + 10*30*40 = 6000 + 12000 = 18000 (minimum)

3. Final Answer:

   18000 -> Option A

4. Quick Check:

   Minimum multiplications = 18000 [OK]

Hint: Check all splits and pick minimum cost [OK]

Common Mistakes:

• Calculating cost for only one parenthesization
• Mixing matrix dimensions order
• Forgetting to add multiplication costs correctly

4. Identify the error in the following TypeScript code snippet for Matrix Chain Multiplication and select the fix:

function 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 + 1; i++) {
      const j = i + L - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k] * p[j];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

medium

A. Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1]

B. Initialize m with Infinity instead of 0

C. Change loop for (let k = i; k <= j; k++) to k < j

D. Return m[0][n] instead of m[0][n - 1]

Solution

1. Step 1: Identify the multiplication cost formula error

   The cost formula uses incorrect indices: p[i] * p[k] * p[j] should use p[k + 1] and p[j + 1] to represent matrix dimensions correctly.

2. Step 2: Confirm other parts are correct

   Initialization with 0 is correct for diagonal, loop ranges are correct, and return index is correct.

3. Final Answer:

   Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1] -> Option A

4. Quick Check:

   Correct cost formula indices fix error [OK]

Hint: Check matrix dimension indices carefully in cost formula [OK]

Common Mistakes:

• Using wrong indices for matrix dimensions in cost calculation
• Changing loop bounds unnecessarily
• Returning wrong matrix cell

5. Given matrices with dimensions [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the Matrix Chain Multiplication approach.

hard

A. 1510

B. 2010

C. 4050

D. 3500

Solution

1. Step 1: Understand matrix dimensions and chain length

   The array represents matrices: 5x10, 10x3, 3x12, 12x5, 5x50, 50x6 (6 matrices).

2. Step 2: Use dynamic programming to find minimum cost

   By calculating all splits and costs:
   - Minimum cost found is 2010 scalar multiplications.

3. Final Answer:

   2010 -> Option B

4. Quick Check:

   Minimum scalar multiplications = 2010 [OK]

Hint: Use DP table to check all splits and pick minimum [OK]

Common Mistakes:

• Calculating only one split option
• Mixing up matrix dimensions order
• Forgetting to add multiplication costs for subproblems