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].