Course contentsShow
← Computer Science
Lesson 937 of 2,87222. Dynamic ProgrammingFree lesson

Matrix Chain Multiplication

Minimize scalar multiplications needed to multiply a chain of matrices using interval DP.

Matrix Chain Multiplication

You'll learn how to minimize the cost of multiplying a sequence of matrices by choosing the optimal order of operations.

The Core Problem

When you need to multiply several matrices together, the order matters—not for the final result (matrix multiplication is associative), but for how much work you do. Multiplying matrices of different dimensions costs different amounts of computation.

For example, if you have three matrices A (10×30), B (30×5), and C (5×60):

  • (AB)C costs: (10×30×5) + (10×5×60) = 1,500 + 3,000 = 4,500 operations
  • A(BC) costs: (30×5×60) + (10×30×60) = 9,000 + 18,000 = 27,000 operations

Same result, wildly different cost!

Interval DP Approach

Matrix Chain Multiplication uses interval dynamic programming. Think of it like this: to optimally multiply matrices from position i to j, you try every possible split point k in between. That split divides the problem into two smaller chains.

State definition:

  • dp[i][j] = minimum scalar multiplications needed to multiply matrices from index i to j

Transition: For each position k between i and j:

  • Cost = dp[i][k] + dp[k+1][j] + (cost of multiplying the two resulting matrices)

Base case:

  • dp[i][i] = 0 (single matrix requires no multiplication)

You build solutions for increasing interval lengths: first intervals of length 2, then 3, and so on, until you've solved the entire chain.

Key Takeaway: Matrix Chain Multiplication uses interval DP to find the optimal parenthesization that minimizes scalar multiplications—testing all possible split points and building up from smaller subproblems to the full chain.