Matrix Chain Multiplication

The Matrix Chain Multiplication problem is a classic problem in dynamic programming.

Given a sequence of matrices, the problem is to find the most efficient way to multiply these matrices together.

The efficiency is measured in terms of the total number of scalar multiplications needed to compute the product.

pseudocode:

MatrixChainOrder(p)
    n = length(p) - 1  // Number of matrices
    let m[1..n, 1..n] be a new table
    let s[1..n, 1..n] be a new table



```
    for i = 1 to n
        m[i,i] = 0  // Base case: single matrix has no cost

    for l = 2 to n  // l is the chain length
        for i = 1 to n - l + 1
            j = i + l - 1
            m[i,j] = infinity
            for k = i to j - 1
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
                if q < m[i,j]
                    m[i,j] = q
                    s[i,j] = k  // Record where to split the chain

    return m and s

function matrixChainOrder(dimensions) {
    const n = dimensions.length - 1; // Number of matrices in the sequence
    const dp = []; // Dynamic programming table

    // Initialize the dp table
    for (let i = 0; i <= n; i++) {
        dp[i] = [];
        for (let j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }

    // Fill the dp table
    for (let len = 2; len <= n; len++) {
        for (let i = 1; i <= n - len + 1; i++) {
            const j = i + len - 1;
            dp[i][j] = Number.MAX_SAFE_INTEGER;
            for (let k = i; k <= j - 1; k++) {
                const cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }

    // Return the minimum number of scalar multiplications needed
    return dp[1][n];
}

// Example usage
const dimensions = [10, 20, 30, 40, 50];
const minScalarMultiplications = matrixChainOrder(dimensions);
console.log("Minimum scalar multiplications:", minScalarMultiplications);

In this code:

• matrixChainOrder function takes an array dimensions representing the dimensions of matrices in the sequence.

• It initializes a dynamic programming table dp to store the minimum number of scalar multiplications needed to multiply each subsequence of matrices.

• It iterates through different subsequence lengths and computes the minimum cost for each subsequence using the recurrence relation of the problem.

• Finally, it returns the minimum number of scalar multiplications needed to multiply the entire sequence of matrices.

For example, if you have matrices with dimensions [10, 20, 30, 40, 50], the output would give you the minimum number of scalar multiplications needed to multiply them efficiently.