Matrix Chain Multiplication

Matrix Chain Multiplication

Matrix Chain Multiplication

Problem

You are given a chain of matrices A1, A2, A3, ... An. You must find the cheapest way to multiply them all.

The order of multiplication changes the total work, even though the final answer is the same. So we need to decide where to put the parentheses to get the minimum number of multiplications.

You are given an array nums of size n. The size of matrix Ai is nums[i - 1] x nums[i].

Return the minimum number of multiplications needed to multiply the whole chain.

Examples

Example 1

Input: nums = [10, 15, 20, 25]
Output: 8000

The matrices are:

• A1 is 10 x 15
• A2 is 15 x 20
• A3 is 20 x 25

There are two ways to multiply them:

• A1 * (A2 * A3) needs 11250 multiplications.
• (A1 * A2) * A3 needs 8000 multiplications.

The minimum is 8000.

Example 2

Input: nums = [4, 2, 3]
Output: 24

• There are only two matrices: A1 is 4 x 2 and A2 is 2 x 3.
• There is only one way to multiply them.
• The cost is 4 * 2 * 3 = 24.

Basic Rule You Need to Know

When we multiply a matrix of size a x b with a matrix of size b x c:

• The result has size a x c.
• The number of multiplications is a * b * c.

This one rule is the base of the whole solution.

Main Idea

This problem uses a pattern called Partition DP. We use it when a problem can be split in many ways, and we want the best split.

Let f(i, j) mean: the minimum cost to multiply the matrices from Ai to Aj.

To solve it, we follow these steps:

• Pick a split point k, where i <= k < j.
• Multiply the left part Ai ... Ak first.
• Multiply the right part Ak+1 ... Aj first.
• Then multiply the two results together.
• Try every possible k and keep the smallest cost.

How to Find the Cost of One Split

For a split at k, the total cost has three parts:

• Left part: f(i, k)
• Right part: f(k + 1, j)
• Joining both parts: p[i - 1] * p[k] * p[j]

Why is the joining cost p[i - 1] * p[k] * p[j]?

• The left part (Ai ... Ak) gives one matrix of size p[i - 1] x p[k].
• The right part (Ak+1 ... Aj) gives one matrix of size p[k] x p[j].
• Multiplying these two matrices costs p[i - 1] * p[k] * p[j].

So the formula is:

cost = f(i, k) + f(k + 1, j) + p[i - 1] * p[k] * p[j]

We take the minimum of this cost over all values of k.

Base Case

• If i === j, there is only one matrix.
• We do not need to multiply anything, so the cost is 0.

Why We Need Memoization

The same sub-problem, like f(2, 3), is needed again and again from different splits. If we solve it every time, the work grows very fast.

So we use a table called dp. We save the answer of each f(i, j) the first time we solve it. Next time, we simply read it from the table.

Solution: Recursion + Memoization (Top-Down)

function matrixChainOrder(p) {
    const n = p.length;

    // Initialize memoization table with -1
    const dp = Array.from({ length: n }, () => Array(n).fill(-1));

    function solve(i, j) {
        // Base case: single matrix requires 0 operations
        if (i === j) return 0;

        // Return cached result if available
        if (dp[i][j] !== -1) return dp[i][j];

        let mini = Infinity;

        // Try all possible partitions k
        for (let k = i; k < j; k++) {
            let steps = p[i - 1] * p[k] * p[j] + solve(i, k) + solve(k + 1, j);

            if (steps < mini) {
                mini = steps;
            }
        }

        return (dp[i][j] = mini);
    }

    // Start with the range covering all matrices (1 to n - 1)
    return solve(1, n - 1);
}

How the Code Works

Let us go through the code step by step.

Step 1: Read the Input

• p is the array of dimensions.
• n = p.length. If there are n numbers, there are n - 1 matrices.
• Matrix Ai has size p[i - 1] x p[i].
• Matrices are numbered from 1 to n - 1.

Step 2: Create the dp Table

• dp[i][j] stores the minimum cost to multiply matrices Ai to Aj.
• We fill the whole table with -1. This means "not solved yet".
• We use -1 because a real cost can never be negative.
• Row 0 and column 0 are not used, because matrix numbering starts from 1.

Step 3: Write the solve(i, j) Function

• Check the base case. If i === j, we return 0.
• Check the saved answer. If dp[i][j] is not -1, we already solved it, so we return it.
• Set mini = Infinity. This variable keeps the smallest cost we find. We start with a very big number, so any real cost is smaller.
• Loop over k from i to j - 1. Each value of k is one way to split the chain.
• Calculate steps for each split. We use the formula p[i - 1] * p[k] * p[j] + solve(i, k) + solve(k + 1, j).
• Update mini. If steps is smaller than mini, we save it.
• Save and return. We store mini in dp[i][j] and return it.

Step 4: Start the Recursion

• We call solve(1, n - 1).
• This means: find the best cost to multiply all matrices, from the first to the last.

Dry Run

Let us run the code for p = [10, 15, 20, 25].

Here n = 4, so we have 3 matrices. We call solve(1, 3).

Split at k = 1:

• Left part: solve(1, 1) = 0.
• Right part: solve(2, 3). This is p[1] * p[2] * p[3] = 15 * 20 * 25 = 7500.
• Joining cost: p[0] * p[1] * p[3] = 10 * 15 * 25 = 3750.
• Total: 0 + 7500 + 3750 = 11250.

Split at k = 2:

• Left part: solve(1, 2). This is p[0] * p[1] * p[2] = 10 * 15 * 20 = 3000.
• Right part: solve(3, 3) = 0.
• Joining cost: p[0] * p[2] * p[3] = 10 * 20 * 25 = 5000.
• Total: 3000 + 0 + 5000 = 8000.

Final answer: min(11250, 8000) = 8000.

This matches the expected output. The best way is (A1 * A2) * A3.

Complexity

• Time Complexity: O(n³)
  • n is the length of the array p.
  • There are about n * n different states (i, j).
  • Each state is solved only once, thanks to memoization.
  • Each state runs a loop over k, which takes up to O(n).
  • So the total is n * n * n = O(n³).
• Space Complexity: O(n²)
  • The dp table has n * n cells.
  • The recursion stack also uses up to O(n) extra space.
  • The table is the bigger part, so the total is O(n²).

Without memoization, the same code would take exponential time.

Summary

• This is a Partition DP problem.
• The cost of multiplying an a x b matrix with a b x c matrix is a * b * c.
• solve(i, j) gives the minimum cost to multiply matrices Ai to Aj.
• We try every split point k and take the minimum cost.
• The cost of one split is solve(i, k) + solve(k + 1, j) + p[i - 1] * p[k] * p[j].
• If i === j, the cost is 0, because there is only one matrix.
• The dp table saves answers, so we never solve the same sub-problem twice.
• The solution runs in O(n³) time and uses O(n²) space.