Matrix Chain Multiplication in DSA Typescript - Build from Scratch

Matrix Chain Multiplication

📖 Scenario: You work in a company that optimizes the order of multiplying several matrices to reduce the total number of calculations. Multiplying matrices in different orders can change the total work needed.Your task is to find the minimum number of scalar multiplications needed to multiply a chain of matrices.

🎯 Goal: Build a TypeScript program that uses dynamic programming to find the minimum multiplication cost for a given chain of matrices.

📋 What You'll Learn

Create an array called dimensions representing the dimensions of matrices.

Create a 2D array called dp to store minimum multiplication costs.

Implement nested loops to fill dp using the matrix chain multiplication logic.

Print the minimum multiplication cost stored in dp[1][n-1].

💡 Why This Matters

🌍 Real World

Matrix chain multiplication optimization is used in computer graphics, scientific computing, and database query optimization to reduce computation time.

💼 Career

Understanding dynamic programming and optimization techniques is valuable for software engineers working on performance-critical applications.

1

Setup matrix dimensions array

Create an array called dimensions with these exact values: [40, 20, 30, 10, 30] representing the dimensions of 4 matrices.

DSA Typescript

# Your code here

Hint

Each matrix Ai has dimensions dimensions[i-1] x dimensions[i].

2

Initialize the DP table

Create a 2D array called dp of size dimensions.length by dimensions.length filled with zeros to store minimum multiplication costs.

DSA Typescript

const dimensions: number[] = [40, 20, 30, 10, 30];
// Your code here

Hint

Use Array.from with a mapping function to create a 2D array.

3

Fill the DP table with minimum multiplication costs

Use nested for loops with variables length, i, and k to fill the dp table. For each chain length from 2 to n-1, calculate minimum cost using the formula: dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dimensions[i-1] * dimensions[k] * dimensions[j]), where j = i + length - 1.

DSA Typescript

const dimensions: number[] = [40, 20, 30, 10, 30];
const n: number = dimensions.length;
const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
// Your code here

Hint

Remember to initialize dp[i][j] to a very large number before checking costs.

4

Print the minimum multiplication cost

Write a console.log statement to print the minimum multiplication cost stored in dp[1][dimensions.length - 1].

DSA Typescript

const dimensions: number[] = [40, 20, 30, 10, 30];
const n: number = dimensions.length;
const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

for (let length = 2; length < n; length++) {
    for (let i = 1; i < n - length + 1; i++) {
        let j = i + length - 1;
        dp[i][j] = Number.MAX_SAFE_INTEGER;
        for (let k = i; k < j; k++) {
            let cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j];
            if (cost < dp[i][j]) {
                dp[i][j] = cost;
            }
        }
    }
}
// Your code here

Hint

The minimum multiplication cost is stored in dp[1][n-1].

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