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:

Code
(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:

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

This represents the following matrices:

Code
A = 40 × 20
B = 20 × 30
C = 30 × 10
D = 10 × 30

There are multiple ways to multiply these matrices:

Code
((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:

Code
dp[i][j]

represent the minimum cost needed to multiply matrices from i to j.

For every range:

Code
i ... j

we try every possible split position:

Code
k

such that:

Code
(i...k) and (k+1...j)

The cost becomes:

Mathematically:

Code
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:

Code
split[i][j]

which stores the index k that produced the minimum cost.

Example:

Code
split[1][4] = 3

means the optimal way to multiply matrices from A to D is:

Code
(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:

Code
(i, j)

we create:

Code
(
left_subexpression
right_subexpression
)

using the stored split position.

This recursively generates the required bracket structure.

Example Walkthrough

Input

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

Matrices

Code
A = 40×20
B = 20×30
C = 30×10
D = 10×30

Optimal Sequence

Code
BC

Cost

Code
20 × 30 × 10 = 6000

Then:

Code
A(BC)

Cost:

Code
40 × 20 × 10 = 8000

Then:

Code
(A(BC))D

Cost:

Code
40 × 10 × 30 = 12000

Total Cost

Code
6000 + 8000 + 12000
=
26000

Parenthesization

Code
((A(BC))D)

Java Solution

Java
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

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

Matrices

Code
A = 10×20
B = 20×30
C = 30×40

Possible Parenthesizations

((AB)C)

Cost:

Code
10×20×30 + 10×30×40
=
6000 + 12000
=
18000

(A(BC))

Cost:

Code
20×30×40 + 10×20×40
=
24000 + 8000
=
32000

Minimum Cost

Code
18000

Answer

Code
((AB)C)

Complexity Analysis

Time Complexity

Code
O(n³)

For every chain length, we try every starting index and every possible split position.

Space Complexity

Code
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.