Dynamic Programming • Interval DP

Matrix Chain Multiplication

Determine the most efficient way to multiply a sequence of matrices. The problem is not actually multiplying them, but deciding the order.

Try Interactive Simulator

Overview

Matrix multiplication is associative. (AB)C is the same as A(BC), but the number of scalar multiplications can be wildly different. We must find the optimal parenthesization.

Intervals

This is classic Interval DP. We solve for all small intervals of length 2, then length 3, up to the full array length `N`.

The Split Point 'k'

For any interval `[i, j]`, we try every possible split point `k`. The cost is the cost of the left group, plus the cost of the right group, plus the cost of multiplying the two resulting matrices.

The Array 'p'

The dimensions are given as an array `p`, where matrix `i` has dimensions `p[i-1] x p[i]`. So merging `[i..k]` and `[k+1..j]` costs `p[i-1] * p[k] * p[j]`.

i \ j	M1	M2	M3
M1	0	0	0
M2	0	0	0
M3	0	0	0

Code Tracker

:::

1for (let len = 2; len <= n; len++) {

2 for (let i = 1; i <= n - len + 1; i++) {

3 let j = i + len - 1;

4 dp[i][j] = Infinity;

5 for (let k = i; k < j; k++) {

6 let cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];

7 if (cost < dp[i][j]) dp[i][j] = cost;

8 }

9 }

10}