Matrix Chain Multiplication

Why does the order matter?

Multiplying a p × q matrix by a q × r matrix takes p · q · r multiplications. Matrix multiplication is associative, so (AB)C equals A(BC), but the cost can differ enormously:

A is 10 × 30, B is 30 × 5 and C is 5 × 60:

• (AB)C = 10·30·5 + 10·5·60 = 1,500 + 3,000 = 4,500
• A(BC) = 30·5·60 + 10·30·60 = 9,000 + 18,000 = 27,000

Same answer, six times the work. With more matrices the number of possible bracketings explodes (they are the Catalan numbers: 5 for 4 matrices, 42 for 6, 4,862 for 10), so we need something smarter than trying them all.

The dynamic programming idea

Matrices A₁ … Aₙ have dimensions given by one list p, where Aᵢ is p[i−1] × p[i].

Let m[i][j] be the minimum cost of computing Aᵢ … Aⱼ. The last multiplication splits the chain somewhere, at k: (Aᵢ … Aₖ)(Aₖ₊₁ … Aⱼ). That costs both halves plus multiplying the two results, which have sizes p[i−1] × p[k] and p[k] × p[j]:

m[i][j] = min over i ≤ k < j of   m[i][k] + m[k+1][j] + p[i−1] · p[k] · p[j]
m[i][i] = 0

Short chains must be solved before long ones, so the table is filled by chain length, one diagonal at a time. s[i][j] remembers the best k.

Worked example

p = [40, 20, 30, 10, 30], so A₁ = 40×20, A₂ = 20×30, A₃ = 30×10 and A₄ = 10×30.

Length 2: m[1][2] = 40·20·30 = 24,000; m[2][3] = 20·30·10 = 6,000; m[3][4] = 30·10·30 = 9,000.

Length 3:

• m[1][3]: k = 1 gives 0 + 6,000 + 40·20·10 = 14,000; k = 2 gives 24,000 + 0 + 40·30·10 = 36,000.
• m[2][4]: k = 2 gives 0 + 9,000 + 20·30·30 = 27,000; k = 3 gives 6,000 + 0 + 20·10·30 = 12,000.

Length 4: m[1][4]: k = 1 gives 36,000; k = 2 gives 69,000; k = 3 gives 14,000 + 0 + 40·10·30 = 26,000.

The best order is ((A₁(A₂A₃))A₄) with 26,000 multiplications. The worst order needs 69,000.

Code

def matrix_chain(p):
    n = len(p) - 1
    m = [[0] * (n + 1) for _ in range(n + 1)]
    s = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):                  # chain length
        for i in range(1, n - length + 2):
            j = i + length - 1
            m[i][j] = float("inf")
            for k in range(i, j):                   # try every split
                cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < m[i][j]:
                    m[i][j], s[i][j] = cost, k

    def brackets(i, j):
        return f"A{i}" if i == j else f"({brackets(i, s[i][j])}{brackets(s[i][j] + 1, j)})"

    return m[1][n], brackets(1, n)

print(matrix_chain([40, 20, 30, 10, 30]))           # (26000, '((A1(A2A3))A4)')
print(matrix_chain([30, 35, 15, 5, 10, 20, 25]))    # (15125, '((A1(A2A3))((A4A5)A6))')

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

int main() {
    vector<int> p = {40, 20, 30, 10, 30};
    int n = p.size() - 1;
    vector<vector<long long>> m(n + 1, vector<long long>(n + 1, 0));
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++)
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + 1LL * p[i - 1] * p[k] * p[j]);
        }
    cout << m[1][n];   // 26000
}

Why DP works here

• Optimal substructure: in an optimal bracketing, both halves around the last split are bracketed optimally too. If one were not, swapping in a better one would lower the total.
• Overlapping subproblems: the chain A₂A₃ appears inside many larger chains. The table computes it once.

The same “split an interval at every k” pattern solves other interval DP problems: optimal binary search trees, polygon triangulation, burst balloons and parsing with the CYK algorithm.

Common mistakes

• Using p[i] · p[k] · p[j] instead of p[i−1] · p[k] · p[j]. Aᵢ has p[i−1] rows.
• Filling the table row by row. m[i][j] needs shorter chains first, so fill by chain length.
• Letting k run up to j. The split must leave at least one matrix on each side: i ≤ k < j.
• Thinking the DP multiplies matrices. It only computes costs; the actual multiplication happens afterwards in the chosen order.