Introduction

Matrix Chain Multiplication is the foundation of Interval DP.

You are given:

arr[]

where:

Matrix i = arr[i-1] × arr[i]

Goal:

Find minimum multiplication cost.

Example

arr = [10,20,30,40,30]

Output:

30000

Key Observation

Different multiplication orders produce different costs.

Example:

(A × B) × C ≠ A × (B × C)

Result matrix remains same.

Cost changes.

DP State

dp[i][j] = Minimum cost to multiply matrices from i to j

Transition

Choose partition k:

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + arr[i-1] * arr[k] * arr[j])

This is the core MCM recurrence.

Dry Run

Input:

 arr = [10,20,30,40,30]

Best Parenthesization:

((A×B)×C)×D

Answer:

 30000

Approach 1 : Memoization

Explanation

  1. Pick partition point k.
  2. Solve left side.
  3. Solve right side.
  4. Add multiplication cost.
  5. Store minimum answer.

Approach 2 : Tabulation

Explanation

State:

dp[i][j]

Meaning:

Minimum multiplication cost for interval.

Transition:

Try every partition k.

Practice

Complexity Analysis

MemoizationTime Complexity: O(n³)
Space Complexity: O(n²)

Tabulation
Time Complexity: O(n³)
Space Complexity: O(n²)

Why This Problem is Important

  • Interval DP
  • Partition DP
  • Advanced DP
  • Foundation of Burst Balloons
  • State Design

Common Beginner Mistakes

  • Wrong matrix dimensions
  • Incorrect partition point
  • Wrong interval traversal
  • Missing base cases
  • Confusing matrices with dimensions

Interview Tip

Always explain:

 Choose a partition point k.

Then:

Solve left interval + Solve right interval + Current multiplication cost

This is the entire Interval DP pattern.

Related Questions

  • Burst Balloons
  • Minimum Cost to Cut Stick
  • Palindrome Partitioning II
  • DP on Trees

Final Takeaway

Matrix Chain Multiplication is the foundation of Interval DP.

It teaches:

  • Interval DP
  • Partition DP
  • State Design
  • Cost Optimization

Mastering MCM makes advanced partition-based Dynamic Programming problems much easier to solve.