Tri's external memory

Dynamic Programming Lesson 9 Interval DP (Matrix Chain Multiplication)

3 min read

Problem

Given a sequence of matrices:

A × B × C × D

Find the parenthesization that minimizes the total number of scalar multiplications.

Matrix multiplication is associative:

(A × B) × C
=
A × (B × C)

The final result is identical.

However, the computational cost can be very different.

Example

Matrices:

A = 10 × 100
B = 100 × 5
C = 5 × 50

Option 1

(A × B) × C

Cost:

10 × 100 × 5
+
10 × 5 × 50
 
=
5000
+
2500
 
=
7500

Option 2

A × (B × C)

Cost:

100 × 5 × 50
+
10 × 100 × 50
 
=
25000
+
50000
 
=
75000

Although both produce the same matrix, the second requires ten times more work.

State Design

Define:

dp[l][r]

Meaning:

Minimum cost to multiply
all matrices
from index l to r.

Example:

dp[1][3]

means:

B × C × D

New DP Pattern

Unlike previous lessons:

House Robber
dp[i]
 
LCS
dp[i][j]
 
Knapsack
dp[item][capacity]

Interval DP uses:

dp[left][right]

The two indices describe:

start
end

of a continuous interval.

Splitting an Interval

Suppose:

A B C D

The first split can only occur between adjacent matrices.

Valid splits:

A     | B C D
 
A B   | C D
 
A B C | D

Invalid:

B | A C D
C | A B D

because the order must never change.

General rule:

[l..k]
|
[k+1..r]

where:

l ≤ k < r

Transition

Try every possible split:

k = l ... r-1

Each split produces:

Left interval
+
Right interval
+
Cost of the final multiplication

Choose the minimum.

Conceptually:

dp[l][r]
=
minimum over all split points

Base Case

A single matrix requires no multiplication.

Therefore:

dp[i][i] = 0

Comparison with Previous DP

House Robber

Question:

Rob or skip?

Coin Change

Question:

Which coin should I use?

LCS

Question:

Skip left or skip right?

LIS

Question:

Which previous state should I extend?

Interval DP

Question:

Where should I split the interval?

Key Insight

Interval DP is characterized by:

  • State is a continuous interval.

  • The recurrence tries every possible split point.

  • Each split divides one problem into two smaller interval subproblems.

General pattern:

Problem
↓
 
Choose a split point
 
↓
 
Solve left interval
 
↓
 
Solve right interval
 
↓
 
Combine the two solutions

Common Interval DP Problems

  • Matrix Chain Multiplication

  • Burst Balloons

  • Optimal Binary Search Tree

  • Polygon Triangulation

  • Strange Printer

  • Minimum Cost to Cut a Stick

Lessons Learned

Before designing a DP solution, ask:

What does the state represent?

If the state naturally describes:

a continuous segment

such as:

[l..r]

then Interval DP is often the correct approach.

The hallmark of Interval DP is not moving to the next state, but deciding:

Where should I split this interval?

Graph View

Backlinks