Brackets in Matrix Chain Multiplication

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:

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:

A single matrix is represented by a character.
Matrix 1 → A
Matrix 2 → B
Matrix 3 → C
And so on.

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

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.