Introduction
Matrix Chain Multiplication (MCM) is one of the most important Dynamic Programming problems. The goal is not to perform the matrix multiplication itself but to determine the most efficient order in which the matrices should be multiplied.
The problem becomes interesting because matrix multiplication is associative:
(A × B) × C = A × (B × C)
However, the number of scalar multiplications required can vary significantly depending on the order of multiplication.
Our task is to find the parenthesization that minimizes the total multiplication cost and return the corresponding bracket representation.
Understanding the Problem
Suppose we have the array:
arr = [40, 20, 30, 10, 30]
This represents the following matrices:
A = 40 × 20
B = 20 × 30
C = 30 × 10
D = 10 × 30
There are multiple ways to multiply these matrices:
((AB)C)D
(A(BC))D
(A(B(CD)))
((A(BC))D)
Each arrangement requires a different number of scalar multiplications.
The objective is to find the arrangement with the minimum cost.
Why Greedy Approaches Fail
A common mistake is to always multiply the cheapest adjacent pair first.
This does not guarantee a globally optimal solution because a locally optimal multiplication may create a large intermediate matrix, increasing future costs.
Since every partition affects subsequent computations, we must evaluate all possible split positions.
This naturally leads to Dynamic Programming.
Dynamic Programming Idea
Let:
dp[i][j]
represent the minimum cost needed to multiply matrices from i to j.
For every range:
i ... j
we try every possible split position:
k
such that:
(i...k) and (k+1...j)
The cost becomes:
Cost of the left subchain
Cost of the right subchain
Cost of multiplying both results
Mathematically:
dp[i][j] =
min(
dp[i][k]
+
dp[k+1][j]
+
arr[i-1] * arr[k] * arr[j]
)
For every optimal split, we store the value of k.
This information will later help us reconstruct the bracket structure.
Tracking the Optimal Split
Besides the DP table, we maintain another table:
split[i][j]
which stores the index k that produced the minimum cost.
Example:
split[1][4] = 3
means the optimal way to multiply matrices from A to D is:
(A..C)(D)
By recursively following these split points, we can rebuild the complete parenthesization.
Building the Answer String
Once the DP table is complete:
For every non-leaf range:
(i, j)
we create:
(
left_subexpression
right_subexpression
)
using the stored split position.
This recursively generates the required bracket structure.
Example Walkthrough
Input
arr = [40, 20, 30, 10, 30]
Matrices
A = 40×20
B = 20×30
C = 30×10
D = 10×30
Optimal Sequence
BC
Cost
20 × 30 × 10 = 6000
Then:
A(BC)
Cost:
40 × 20 × 10 = 8000
Then:
(A(BC))D
Cost:
40 × 10 × 30 = 12000
Total Cost
6000 + 8000 + 12000
=
26000
Parenthesization
((A(BC))D)
Java Solution
class Solution {
public String matrixChainOrder(int arr[]) {
int n = arr.length;
int[][] dp = new int[n][n];
int[][] split = new int[n][n];
for (int len = 2; len < n; len++) {
for (int i = 1; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost =
dp[i][k]
+ dp[k + 1][j]
+ arr[i - 1] * arr[k] * arr[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
split[i][j] = k;
}
}
}
}
return build(1, n - 1, split);
}
private String build(int i, int j, int[][] split) {
if (i == j) {
return String.valueOf((char)('A' + i - 1));
}
int k = split[i][j];
return "("
+ build(i, k, split)
+ build(k + 1, j, split)
+ ")";
}
}
Dry Run
Input
arr = [10, 20, 30, 40]
Matrices
A = 10×20
B = 20×30
C = 30×40
Possible Parenthesizations
((AB)C)
Cost:
10×20×30 + 10×30×40
=
6000 + 12000
=
18000
(A(BC))
Cost:
20×30×40 + 10×20×40
=
24000 + 8000
=
32000
Minimum Cost
18000
Answer
((AB)C)
Complexity Analysis
Time Complexity
O(n³)
For every chain length, we try every starting index and every possible split position.
Space Complexity
O(n²)
For the DP and split tables.
Key Insight
The heart of the problem is realizing that the result depends entirely on where we place the brackets. Dynamic Programming helps us compute the minimum multiplication cost for every subchain, while the split table preserves the decisions needed to reconstruct the optimal parenthesization. Instead of merely finding the minimum cost, we use those stored decisions to generate the exact bracket expression required by the problem.
Summary
Matrix Chain Multiplication is a classic Dynamic Programming problem that focuses on finding the most efficient order of matrix multiplication rather than performing the multiplication itself. By evaluating all possible partition points for every matrix subchain and storing the optimal split positions, we can compute the minimum multiplication cost and reconstruct the corresponding parenthesization. The solution uses a DP table for cost calculation and a split table for expression reconstruction, achieving O(n³) time complexity and O(n²) space complexity.