Matrix Chain Multiplication — Interval DP

The problem

Matrices A₁(5×10) × A₂(10×3) × A₃(3×12). Cost of (A₁A₂)A₃ = 150 + 180 = 330. Cost of A₁(A₂A₃) = 360 + 600 = 960.

The problem

Matrices A₁(5×10) × A₂(10×3) × A₃(3×12). Cost of (A₁A₂)A₃ = 150 + 180 = 330. Cost of A₁(A₂A₃) = 360 + 600 = 960.

State

dp[i][j] = min cost to compute product of matrices i through j.

Transition

for (int len = 2; len <= n; len++)
  for (int i = 0; i + len <= n; i++) {
    int j = i + len - 1;
    dp[i][j] = INF;
    for (int k = i; k < j; k++)
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]);
  }

Complexity

O(N³). Three nested loops. Interval DP is inherently more expensive than linear.