JavaScript Coding Test Course, Finding the Minimum Number of Matrix Multiplications

Problem Description

This problem requires finding the minimum number of operations needed to multiply a given N matrices.
The number of operations for matrix multiplication greatly varies based on the order of multiplication, and thus it is necessary to find the correct order.

When the size of matrix A is p × q and the size of matrix B is q × r,
the number of operations for multiplying the two matrices is p × q × r.
When multiplying several matrices at once, an efficient multiplication order must be found.

For instance, when multiplying three matrices of sizes 10 × 20, 20 × 30, 30 × 40,
the operation count for (10×20) * (20×30) * (30×40) is 10 × 20 × 30 + 10 × 30 × 40 = 6000 + 12000 = 18000.
If we multiply in the order of (10×30) * (30×40) * (20×30), the operation count becomes 10 × 30 × 40 + 10 × 20 × 40 = 12000 + 8000 = 20000.
Here, we can see that the order of the first case is more efficient.

Input Format

The first line contains the number of matrices N. (1 ≤ N ≤ 100)

The second line contains N + 1 integers separated by spaces.
The i-th integer represents the size of the matrix A[i] × A[i+1].
(1 ≤ A[i] ≤ 500)

Output Format

Print the minimum number of operations required as a single integer.

Problem Solving Process

Step 1: Understanding Dynamic Programming Technique

This question is an optimization problem for matrix multiplication, which can be solved using dynamic programming.
To find the minimum, a 2D array can be used to store the number of operations for each ordering of matrix multiplication.

Step 2: Initializing the Array

First, receive an array m representing N matrices. The length of this array is N + 1.
It stores the dimension information of each matrix.

let m = [10, 20, 30, 40];
        

Next, declare a 2D array dp to store the number of operations, initialized to Infinity.
The diagonal elements are set to 0.

let dp = Array.from(Array(n), () => Array(n).fill(Infinity));
for (let i = 0; i < n; i++) {
    dp[i][i] = 0;
}
        

Step 3: Completing the Dynamic Programming Table

Using a nested loop, partition the matrices and calculate the minimum number of operations for each multiplication.
The outer loop represents the length of the multiplication chain, while the inner loop represents the indices attempting the multiplications.

for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
        let j = i + len - 1;
        for (let k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + m[i] * m[k + 1] * m[j + 1]);
        }
    }
}
        

Step 4: Outputting the Result

Finally, print the value of the one-dimensional array dp[0][n – 1] to check the minimum.

console.log(dp[0][n - 1]);
        

Complete Code Example

function matrixChainOrder(m) {
    const n = m.length - 1;
    let dp = Array.from(Array(n), () => Array(n).fill(Infinity));
    
    for (let i = 0; i < n; i++) {
        dp[i][i] = 0;
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1;
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + m[i] * m[k + 1] * m[j + 1]);
            }
        }
    }

    return dp[0][n - 1];
}

let m = [10, 20, 30, 40]; // Matrix sizes
console.log(matrixChainOrder(m)); // Output