Matrix Chain Multiplication · Algorithms (DAA)

Multiplying a p × q matrix by a q × r matrix takes p·q·r scalar multiplications. Matrix multiplication is associative — (AB)C = A(BC) — but the cost depends on the order.

Example: A is 10 × 100, B is 100 × 5, C is 5 × 50.

Order	Cost
(AB)C	10·100·5 + 10·5·50 = 5,000 + 2,500 = 7,500
A(BC)	100·5·50 + 10·100·50 = 25,000 + 50,000 = 75,000

Ten times difference for three matrices. For a chain of n matrices, the number of parenthesisations grows exponentially (the Catalan numbers), so we use DP.

Recurrence

Matrix Aᵢ has dimensions p[i−1] × p[i]. State: m[i][j] = minimum cost to multiply Aᵢ … Aⱼ.

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

Split the chain after Aₖ: multiply the left part, the right part, then the two results. Store the best k in s[i][j] to rebuild the parenthesisation.

Fill order: by increasing chain length L = 2, 3, …, n (each cell needs shorter chains).

C++

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

vector<vector<int>> s;
string paren(int i, int j) {
    if (i == j) return "A" + to_string(i);
    return "(" + paren(i, s[i][j]) + paren(s[i][j] + 1, j) + ")";
}

int main() {
    vector<int> p = {30, 35, 15, 5, 10, 20, 25};     // A1: 30x35, A2: 35x15, ..., A6: 20x25
    int n = p.size() - 1;
    vector<vector<long>> m(n + 1, vector<long>(n + 1, 0));
    s.assign(n + 1, vector<int>(n + 1, 0));
    for (int L = 2; L <= n; L++)
        for (int i = 1; i + L - 1 <= n; i++) {
            int j = i + L - 1;
            m[i][j] = LONG_MAX;
            for (int k = i; k < j; k++) {
                long cost = m[i][k] + m[k + 1][j] + (long)p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }
    cout << "minimum scalar multiplications: " << m[1][n] << endl;
    cout << "optimal order: " << paren(1, n) << endl;
    cout << "m[2][5] = " << m[2][5] << endl;
    return 0;
}

Output

minimum scalar multiplications: 15125
optimal order: ((A1(A2A3))((A4A5)A6))
m[2][5] = 7125

Try it Yourself

This is the classic CLRS example: the answer is 15,125 with ((A1(A2A3))((A4A5)A6)).

Time O(n³) (n² cells, each trying up to n splits), space O(n²).

Test yourself

4 questions · pick an answer to check it instantly

1
What is the cost of multiplying a 4 × 6 matrix by a 6 × 3 matrix?
2
In what order is the m table filled?
3
What is the time complexity of the matrix-chain DP?
4
What does s[i][j] store?

#Recurrence

Test yourself

Recurrence