DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)

Matrix Chain Multiplication

Find the optimal parenthesization to minimize scalar multiplications. Watch the DP table fill diagonally as subproblems of increasing chain length are solved.

Time: O(n³)

Space: O(n²)

Interval DP

Optimal Parenthesization

Dimension array (n+1 values for n matrices — e.g. "30 35 15 5" = M1:30×35, M2:35×15, M3:15×5)

Speed: 800ms

FastSlow

Step 1 / 0

Matrix chain

M130×35

M235×15

M315×5

M45×10

DP Table — m[i][j] = min cost for M_i…M_j

Active cell

New best

Left subgroup

Right subgroup

Optimal

Click Play to begin.

Algorithm Details

Time:O(n³)

Space:O(n²)

Type:Interval DP

Fill order:By chain length

Key Concepts

Recurrence: m[i][j] = min over k: m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j]
Base case: m[i][i] = 0
Fill order: chain length l = 2, 3, …, n
Answer: m[1][n] with parenthesization from s[i][j]

Knowledge Check

Question 1 of 3

Why does MCM fill the DP table diagonally?

DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)

DSAverse

DSAverse

Matrix Chain Multiplication

Matrix chain

DP Table — m[i][j] = min cost for Mi…Mj

Algorithm Details

Key Concepts

Knowledge Check

DSAverse

Matrix Chain Multiplication

Matrix chain

DP Table — m[i][j] = min cost for Mi…Mj

Algorithm Details

Key Concepts

Knowledge Check

DP Table — m[i][j] = min cost for M_i…M_j

DP Table — m[i][j] = min cost for M_i…M_j