Matrix Chain Multiplication

Matrix Chain Multiplication

Now that we've covered Fibonacci Series, Longest Common Subsequence, and the 0/1 Knapsack Problem, you're ready for a classic final DP pattern: interval DP.

Matrix Chain Multiplication asks:

Given several matrices in a fixed order, where should we place parentheses so multiplication costs the least?

This is not about changing the order of matrices. Like a well-planned anime battle combo, the characters attack in the same sequence — but the grouping changes everything.

By the end, you'll be able to:

• Define DP states over ranges like i..j
• Try every possible split point inside an interval
• Build a bottom-up table by increasing chain length
• Recover the actual optimal parenthesization

This wraps up the course by combining the DP instincts you've built: state design, recurrence, tabulation, and solution recovery.

Why Parentheses Matter

Suppose we have matrices:

A: 10 x 30
B: 30 x 5
C: 5 x 60

The multiplication order is fixed: A B C.

But there are two ways to parenthesize:

(A B) C
A (B C)

Their scalar multiplication costs differ:

(A B) C:
  A*B costs 10*30*5 = 1500
  result is 10x5
  (AB)*C costs 10*5*60 = 3000
  total = 4500

A (B C):
  B*C costs 30*5*60 = 9000
  result is 30x60
  A*(BC) costs 10*30*60 = 18000
  total = 27000

Same matrices. Same order. Wildly different cost.

We encode the dimensions as:

dims = [10, 30, 5, 60]

Matrix A_i has dimensions:

dims[i] x dims[i+1]

For matrices with dimensions:

A: 10 x 30
B: 30 x 5
C: 5 x 60

Which parenthesization is cheaper?

The DP State

Unlike Knapsack, where the state tracked an item index and remaining capacity, Matrix Chain Multiplication tracks an interval.

Let:

dp[i][j] = minimum cost to multiply matrices A_i through A_j

If i == j, there is only one matrix, so no multiplication is needed:

dp[i][i] = 0

For longer intervals, we try every split point k:

A_i ... A_k   and   A_{k+1} ... A_j

Then combine the two results.

The recurrence:

dp[i][j] = min over k from i to j-1 of:
           dp[i][k]
         + dp[k+1][j]
         + dims[i] * dims[k+1] * dims[j+1]

That last term is the cost of multiplying the two resulting matrices after both sides are already optimized.

Fill in the blank.

In Matrix Chain Multiplication, the table entry representing the minimum cost to multiply matrices A_i through A_j is usually written as _____.

Building by Chain Length

Just like the bottom-up LCS table depended on smaller already-computed subproblems, Matrix Chain Multiplication fills intervals from short to long.

Order of computation:

1. Length 1: cost is 0
2. Length 2: one possible split
3. Length 3+: try all split points

Here's a complete implementation.

```python
from math import inf


def matrix_chain_cost(dims):
    """Return the minimum scalar multiplication cost.

    dims length is n + 1 for n matrices.
    Matrix i has shape dims[i] x dims[i + 1].
    """
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

    # chain_len is the number of matrices in the interval
    for chain_len in range(2, n + 1):
        for i in range(n - chain_len + 1):
            j = i + chain_len - 1
            dp[i][j] = inf

            for k in range(i, j):
                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i] * dims[k + 1] * dims[j + 1]
                )
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]


print(matrix_chain_cost([10, 30, 5, 60]))
print(matrix_chain_cost([40, 20, 30, 10, 30]))
```

True or false?

Matrix Chain Multiplication lets us reorder matrices however we want, as long as the final dimensions are compatible.

Returning the Actual Plan

A minimum cost is useful, but interviewers may also ask for the parenthesization.

This is the same idea you saw in Longest Common Subsequence when recovering one LCS: store the decision that led to the best value.

Here, we store the best split point k in a separate table called split.

```python
from math import inf


def matrix_chain_order(dims):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    split = [[None] * n for _ in range(n)]

    for chain_len in range(2, n + 1):
        for i in range(n - chain_len + 1):
            j = i + chain_len - 1
            dp[i][j] = inf

            for k in range(i, j):
                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i] * dims[k + 1] * dims[j + 1]
                )
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k

    def build_parentheses(i, j):
        if i == j:
            return f"A{i}"
        k = split[i][j]
        left = build_parentheses(i, k)
        right = build_parentheses(k + 1, j)
        return f"({left} x {right})"

    return dp[0][n - 1], build_parentheses(0, n - 1)


cost, order = matrix_chain_order([40, 20, 30, 10, 30])
print("Minimum cost:", cost)
print("Best order:", order)
```

For n matrices, what is the time complexity of the standard bottom-up Matrix Chain Multiplication DP?

What You Just Completed

Matrix Chain Multiplication is a fitting final lesson because it highlights a new DP shape: intervals.

Across this course, you've now seen several major DP styles:

• Fibonacci Series: one-dimensional recurrence and space compression
• Longest Common Subsequence: two-dimensional grid DP and solution recovery
• 0/1 Knapsack Problem: choice-based DP with capacity constraints
• Matrix Chain Multiplication: interval DP with split points

A strong DP workflow now looks familiar:

1. Define the state
2. Identify base cases
3. Write the recurrence
4. Choose top-down or bottom-up
5. Track decisions if the actual solution is needed
6. Analyze time and space

The real skill is not memorizing formulas. It's recognizing the story each problem is telling.

When a problem asks for the best way to split a sequence into parts, think of today's lesson. The final boss may look intimidating, but you now have the DP toolkit to read its attack pattern.