Skip to main content
Interval DP

Matrix Chain Multiplication

Find the optimal order to multiply matrices to minimize total operations. dp[i][j] = min cost to multiply matrices i through j. Try every split point k: dp[i][k] + dp[k+1][j] + cost of multiplying the two results.

O(n³)
·
O(n²)

How It Works

Matrix Chain Multiplication finds the parenthesization of a matrix product that minimizes scalar multiplications. Matrix multiplication is associative, so the result is fixed, but cost varies wildly with order. Define dp[i][j] as the cheapest way to multiply matrices i through j. Try every split point k: the left part costs dp[i][k], the right part dp[k+1][j], and combining them costs rows_i × cols_k × cols_j, the dimensions of the two resulting matrices.

Filling intervals from length 2 upward evaluates O(n^2) ranges with O(n) splits each — O(n^3) time and O(n^2) space, versus the Catalan-number count of parenthesizations for brute force. This split-and-combine shape is the archetype for interval DP problems such as polygon triangulation and boolean expression parenthesization.

Step-by-Step Visualization

Matrix chain: dims [10,20,30,40] → 3 matrices
10
0
20
1
30
2
40
3
Matrices10x20, 20x30, 30x40
1/3

Code

Java
static int matrixChainOrder(int[] dims) {
  int n = dims.length - 1;
  int[][] dp = new int[n][n];

  for (int len = 2; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
      int j = i + len - 1;
      dp[i][j] = Integer.MAX_VALUE;
      for (int k = i; k < j; k++)
        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]);
    }
  return dp[0][n-1];
}

Tips & Gotchas

1dp[i][j] = min operations to multiply matrices i through j
2Try every split point k: cost = dp[i][k] + dp[k+1][j] + dims
3Iterate by increasing chain length

Practice Problems

  • 1Matrix Chain Multiplication
  • 2Burst Balloons
  • 3Minimum Score Triangulation of Polygon
  • 4Minimum Cost Tree From Leaf Values

About the Interval DP Pattern

Solve subproblems on every contiguous range [i..j]. The outer loop iterates over range lengths, the inner loops over starting positions. At each range, try every possible split point to find the optimum.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

Why does multiplication order change the cost if the result is the same?

Multiplying a p×q by a q×r matrix costs p·q·r scalar operations, so intermediate shapes matter enormously. For dimensions 10×100, 100×5, 5×50, one order costs 7,500 operations while the other costs 75,000 — a 10x gap from parenthesization alone.

How is the dimensions array indexed in the recurrence?

With dims of length n+1, matrix i has shape dims[i-1] × dims[i]. Splitting range [i..j] at k costs dims[i-1] · dims[k] · dims[j] to merge the halves. Off-by-one mistakes here are the most frequent implementation bug.

What signals that a problem is interval DP rather than linear DP?

The answer for a range depends on choosing an internal split, merge, or last-operation point, and the cost of combining depends on the range boundaries. Whenever removing or grouping middle elements changes neighbors' interactions, think intervals, not prefixes.