Log inSign up
hardGeeksforGeeksNot Started

Matrix Chain Multiplication

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array p representing dimensions of a sequence of matrices, where the i-th matrix A_i has dimensions p[i - 1] × p[i] for 1 <= i < n.

Find the minimum number of scalar multiplications needed to multiply the chain of matrices A_1 × A_2 × \dots × A_{n - 1}.

Multiplying two matrices of dimensions A (r × c) and B (c × k) requires r × c × k scalar multiplications.

### Example 1 - Input: p = [40, 20, 30, 10, 30] - Output: 26000 - Explanation: - A_1 is 40 × 20, A_2 is 20 × 30, A_3 is 30 × 10, A_4 is 10 × 30. - Optimal parenthesization: ((A_1 × (A_2 × A_3)) × A_4). - Operations: - A_2 × A_3: 20 × 30 × 10 = 6000 (result is 20 × 10) - A_1 × (A_2 A_3): 40 × 20 × 10 = 8000 (result is 40 × 10) - (A_1 A_2 A_3) × A_4: 40 × 10 × 30 = 12000 - Total = 6000 + 8000 + 12000 = 26000.

### Example 2 - Input: p = [10, 20, 30] - Output: 6000 - Explanation: Single multiplication: 10 × 20 × 30 = 6000.

Constraints:

  • 2 <= p.length <= 100
  • 1 <= p[i] <= 500

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the fundamental Matrix Chain Multiplication interval recurrence.
  • Understand why subproblem dependencies necessitate length-based outer iteration.
  • Implement the classic 3-nested loop interval tabulation pattern.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding optimal parenthesization or tree factorization of associative operations.
  • Splitting a range (i, j) at partition point k into two independent sub-ranges (i, k) and (k+1, j).

Algorithmic Decision Tree:

  • Interval DP -> outer loop over length L, inner loop over split k.
  • Combine costs of left interval, right interval, and merging cost.

Connected Patterns:

Burst BalloonsOptimal Binary Search TreeMinimum Cost to Merge Stones

1. Recursive Exhaustive Partitioning

Intuition

At each interval (i, j), test every possible split point k from i to j-1 recursively.

Algorithm

  1. Define solve(i, j).
  2. If i == j, return 0.
  3. Initialize minCost = infinity.
  4. For k = i to j - 1:
  5. cost = solve(i, k) + solve(k + 1, j) + p[i - 1] * p[k] * p[j]
  6. minCost = min(minCost, cost).
  7. Return minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int solveRec(int i, int j, const vector<int>& p) {
8 if (i == j) return 0;
9 int minCost = 1e9;
10 for (int k = i; k < j; k++) {
11 int cost = solveRec(i, k, p) + solveRec(k + 1, j, p) + p[i - 1] * p[k] * p[j];
12 minCost = min(minCost, cost);
13 }
14 return minCost;
15}
16
17int matrixMultiplicationRec(vector<int>& p) {
18 int n = p.size();
19 return solveRec(1, n - 1, p);
20}
21
22int main() {
23 vector<int> p = {40, 20, 30, 10, 30};
24 cout << "Min Multiplications (Recursive): " << matrixMultiplicationRec(p) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(4^n / n^(3/2)) (Catalan growth)
  • Space complexity: O(n) call stack

2. Memoized Top-Down Interval DP

Intuition

Cache results of solve(i, j) in a 2D memo table initialized to -1.

Algorithm

  1. Create memo matrix of size n x n filled with -1.
  2. Base Case: If i == j, return 0.
  3. If memo[i][j] != -1, return memo[i][j].
  4. Loop k from i to j - 1, tracking min cost.
  5. Store and return memo[i][j] = minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cstring>
5
6using namespace std;
7
8int memo[105][105];
9
10int solveMemo(int i, int j, const vector<int>& p) {
11 if (i == j) return 0;
12 if (memo[i][j] != -1) return memo[i][j];
13
14 int minCost = 1e9;
15 for (int k = i; k < j; k++) {
16 int cost = solveMemo(i, k, p) + solveMemo(k + 1, j, p) + p[i - 1] * p[k] * p[j];
17 minCost = min(minCost, cost);
18 }
19 return memo[i][j] = minCost;
20}
21
22int matrixMultiplicationMemo(vector<int>& p) {
23 int n = p.size();
24 memset(memo, -1, sizeof(memo));
25 return solveMemo(1, n - 1, p);
26}
27
28int main() {
29 vector<int> p = {40, 20, 30, 10, 30};
30 cout << "Min Multiplications (Memoized): " << matrixMultiplicationMemo(p) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2) memo table and O(n) call stack

3. Bottom-Up Interval Tabulation O(n^3)

Intuition

Build table dp[n][n]. Outer loop iterates chain length L from 2 to n - 1, ensuring smaller sub-chains are computed before larger chains.

Algorithm

  1. Let n = p.length.
  2. Create dp of size n x n filled with 0.
  3. For L = 2 to n - 1 (chain length):
  4. For i = 1 to n - L:
  5. j = i + L - 1
  6. dp[i][j] = infinity
  7. For k = i to j - 1:
  8. cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
  9. dp[i][j] = min(dp[i][j], cost)
  10. Return dp[1][n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int matrixMultiplicationOptimal(vector<int>& p) {
8 int n = p.size();
9 vector<vector<int>> dp(n, vector<int>(n, 0));
10
11 for (int L = 2; L < n; L++) {
12 for (int i = 1; i < n - L + 1; i++) {
13 int j = i + L - 1;
14 dp[i][j] = 1e9;
15 for (int k = i; k < j; k++) {
16 int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
17 dp[i][j] = min(dp[i][j], cost);
18 }
19 }
20 }
21 return dp[1][n - 1];
22}
23
24int main() {
25 vector<int> p = {40, 20, 30, 10, 30};
26 cout << "Min Multiplications (Optimal Tabulation): " << matrixMultiplicationOptimal(p) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2) 2D table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive PartitioningO(4^n / n^(3/2))O(n)Exhaustive branching over split points k.Redundant sub-chain calls
2.Memoized Interval DPO(n^3)O(n^2)Top-down memoization of interval (i, j).Call stack
3.Bottom-Up TabulationOptimalO(n^3)O(n^2)Outer loop over chain length L from 2 to n-1.Triple nested loop

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating i from 0 to n without length-based ordering (tries to access uncomputed future states).

Pitfall 2:

Off-by-one with matrix indices: Matrix i has dimension p[i-1] x p[i].

Crucial Edge Cases to Validate:

  • p.length = 2: Single matrix, 0 multiplications needed.
  • p.length = 3: Two matrices, exactly p[0] * p[1] * p[2] operations.
  • Identical dimensions: Recurrence executes normally.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Cite this problem as the universal blueprint for Interval DP: Burst Balloons, Minimum Cost to Merge Stones, and Optimal Binary Search Tree all inherit this exact 3-nested loop structure.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the outer loop in bottom-up Matrix Chain Multiplication iterate over chain length L rather than row index i?

Back to DSA Sheet