SyntaxPilot
Courses/DSA and Coding Problems/Lesson 75
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 75 of 90

Matrix chain multiplication

queued

These are the notes for DSA episode 75. A camera app runs a chain of filter matrices on every photo. (AB)C and A(BC) give exactly the same picture, but one needs 4,500 multiplications and the other 27,000. Which bracketing is cheapest? We learn what one product costs (p · q · r), try the cheapest pair first (a wrong answer on screen: 36,000 instead of 26,000), then every last split recursively (correct, then Time Limit Exceeded on 24 matrices), and find the insight: the last multiplication splits the chain into two independent parts, just like the last balloon in episode 74. Then the interval DP typed live, with a split table that prints the brackets, 300 matrices in milliseconds and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The camera app In code
A filter (rotate, resize, colour) a matrix
Its shape rows × columns: matrix i is p[i-1] × p[i]
The filter chain A × B × C × ...
Same photo, any bracketing matrix multiplication is associative
Different amount of work the bracketing decides the cost

Every word, from zero

  • Matrix: a grid of numbers with rows × columns. A 10 × 30 matrix has 10 rows and 30 columns.
  • Matrix product: a p × q matrix times a q × r matrix gives a p × r matrix. The inner sizes must match.
  • Cost of one product: each of the p · r result cells is a row times a column, q multiplications, so p · q · r in total.
  • Associative: (AB)C = A(BC). The brackets don't change the answer, only the work.
  • Bracketing (parenthesization): the order the products are done in, written with brackets, e.g. ((A(BC))D).
  • Dimension array p: n matrices are described by n + 1 numbers; matrix i is p[i-1] × p[i].
  • Sub-chain: consecutive matrices i..j.
  • Split point k: the last product joins (i..k) and (k+1..j).
  • Interval DP: a DP whose state is a range, solved through a split point inside it.
  • Split table: split[i][j] stores the best k, so the brackets can be rebuilt afterwards.

Problem statement

Matrix chain multiplication. Given p[0..n], where matrix i (1-based) is p[i-1] × p[i], return the minimum number of scalar multiplications needed to compute A1 × A2 × ... × An, and a bracketing that achieves it.

p Matrices Answer Brackets
{10, 30, 5, 60} 10×30, 30×5, 5×60 4500 ((AB)C)
{40, 20, 30, 10, 30} 40×20, 20×30, 30×10, 10×30 26000 ((A(BC))D)
{10, 20, 30} two matrices 6000 (AB)
{10, 20} one matrix 0 A
{5, 5, 5, 5} three 5×5 250 either

(AB)C for the camera chain: 10·30·5 + 10·5·60 = 1500 + 3000 = 4500. A(BC): 30·5·60 + 10·30·60 = 9000 + 18000 = 27000.

Obvious idea 1: the cheapest pair first

Multiplying neighbours i and i+1 removes the shared middle size from the list. Always do the cheapest one now?

import java.util.*;

public class Main {
    static int minCost(int[] dims) {
        List<Integer> p = new ArrayList<>();
        for (int d : dims) p.add(d);
        int total = 0;
        while (p.size() > 2) {
            int best = 1;
            for (int i = 1; i < p.size() - 1; i++)
                if (p.get(i - 1) * p.get(i) * p.get(i + 1)
                        < p.get(best - 1) * p.get(best) * p.get(best + 1)) best = i;
            total += p.get(best - 1) * p.get(best) * p.get(best + 1);
            p.remove(best);
        }
        return total;
    }
    public static void main(String[] args) {
        System.out.println(minCost(new int[]{10, 30, 5, 60}));
        System.out.println(minCost(new int[]{40, 20, 30, 10, 30}));
    }
}
4500
36000

36,000 instead of 26,000. Greedy did BC (6,000, right), then (BC)D (6,000), and was left with A × (BCD), a 40·20·30 = 24,000 product. A cheap step now forced an expensive one later.

Obvious idea 2: try every last split

The last product joins a left part i..k and a right part k+1..j. Try every k, recursively.

import java.util.*;

public class Main {
    static int minCost(int[] p) {
        return best(p, 1, p.length - 1);
    }
    static int best(int[] p, int i, int j) {
        if (i == j) return 0;
        int min = Integer.MAX_VALUE;
        for (int k = i; k < j; k++)
            min = Math.min(min, best(p, i, k) + best(p, k + 1, j)
                                + p[i - 1] * p[k] * p[j]);
        return min;
    }
    public static void main(String[] args) {
        System.out.println(minCost(new int[]{10, 30, 5, 60}));
        System.out.println(minCost(new int[]{40, 20, 30, 10, 30}));
        System.out.println(minCost(new int[]{10, 20, 30}));
        System.out.println(minCost(new int[]{10, 20}));
        System.out.println(minCost(new int[]{5, 5, 5, 5}));
    }
}
4500
26000
6000
0
250

Correct. Now 24 matrices:

import java.util.*;

public class Main {
    static int minCost(int[] p) {
        return best(p, 1, p.length - 1);
    }
    static int best(int[] p, int i, int j) {
        if (i == j) return 0;
        int min = Integer.MAX_VALUE;
        for (int k = i; k < j; k++)
            min = Math.min(min, best(p, i, k) + best(p, k + 1, j)
                                + p[i - 1] * p[k] * p[j]);
        return min;
    }
    public static void main(String[] args) {
        int[] p = new int[25];
        for (int i = 0; i < 25; i++) p[i] = i % 7 * 5 + 5;
        long t0 = System.nanoTime();
        int c = minCost(p);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("24 matrices: " + c + ", " + ms + " ms");
    }
}

(no output: still running after 25 s: Time Limit Exceeded)

Why is it slow?

  • best(i, j) depends only on two numbers, but the same sub-chain is asked for by many bigger chains (BC is inside ABC, BCD, ABCD, ...).
  • Each extra matrix makes the recursion about three times slower (20 matrices took about 2 seconds on our machine).
  • There are only about n²/2 sub-chains: 300 for 24 matrices. A table can solve each once.

The key insight: the last product splits the chain

dp[i][i] = 0
dp[i][j] = min over i <= k < j of   dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
answer   = dp[1][n]

The left part becomes a p[i-1] × p[k] matrix, the right part a p[k] × p[j] matrix, so the last product costs p[i-1]·p[k]·p[j]. Each part is bracketed on its own: independent, like the walls of burst balloons. Fill by chain length so shorter chains are ready first, and keep split[i][j] = k to print the brackets.

By hand: p = [40, 20, 30, 10, 30]

Sub-chain Splits tried dp
A, B, C, D one matrix 0
AB — 40·20·30 = 24000
BC — 20·30·10 = 6000
CD — 30·10·30 = 9000
ABC A(BC): 0 + 6000 + 40·20·10 = 14000; (AB)C: 24000 + 0 + 40·30·10 = 36000 14000
BCD B(CD): 0 + 9000 + 20·30·30 = 27000; (BC)D: 6000 + 0 + 20·10·30 = 12000 12000
ABCD A(BCD): 12000 + 24000 = 36000; (AB)(CD): 24000 + 9000 + 36000 = 69000; (ABC)D: 14000 + 12000 = 26000 26000

Following the splits: ((A(BC))D).

Solution in Java

import java.util.*;

public class Main {
    static int[][] split;
    static int minCost(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n + 1][n + 1];
        split = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; 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] + p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        return dp[1][n];
    }
    static String brackets(int i, int j) {
        if (i == j) return String.valueOf((char) ('A' + i - 1));
        int k = split[i][j];
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
    }
    public static void main(String[] args) {
        int[][] tests = {{10, 30, 5, 60}, {40, 20, 30, 10, 30},
                         {10, 20, 30}, {10, 20}, {5, 5, 5, 5}};
        for (int[] p : tests) {
            int c = minCost(p);
            System.out.println(c + "  " + brackets(1, p.length - 1));
        }
    }
}
4500  ((AB)C)
26000  ((A(BC))D)
6000  (AB)
0  A
250  (A(BC))

The 24 matrices that timed out, and 100 and 300 random matrices:

import java.util.*;

public class Main {
    static int[][] split;
    static int minCost(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n + 1][n + 1];
        split = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; 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] + p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        return dp[1][n];
    }
    static String brackets(int i, int j) {
        if (i == j) return String.valueOf((char) ('A' + i - 1));
        int k = split[i][j];
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
    }
    public static void main(String[] args) {
        int[] p = new int[25];
        for (int i = 0; i < 25; i++) p[i] = i % 7 * 5 + 5;
        long t0 = System.nanoTime();
        int c = minCost(p);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("24 matrices: " + c + ", " + ms + " ms");
        for (int n : new int[]{100, 300}) {
            int[] q = new int[n + 1];
            Random rnd = new Random(1);
            for (int i = 0; i <= n; i++) q[i] = rnd.nextInt(10) + 1;
            t0 = System.nanoTime();
            c = minCost(q);
            ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(n + " matrices: " + c + ", " + ms + " ms");
        }
    }
}
24 matrices: 44750, 0 ms
100 matrices: 3266, 7 ms
300 matrices: 10196, 35 ms

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Matrix chain multiplication: matrix i is p[i-1] x p[i]; dp[i][j] = cheapest cost to multiply matrices i..j.
vector<vector<int>> split_;

int minCost(const vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    split_.assign(n + 1, vector<int>(n + 1, 0));
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {           // the LAST product joins (i..k) and (k+1..j)
                int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < dp[i][j]) { dp[i][j] = cost; split_[i][j] = k; }
            }
        }
    return dp[1][n];
}

string brackets(int i, int j) {
    if (i == j) return string(1, char('A' + i - 1));
    int k = split_[i][j];
    return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
}

int main() {
    vector<vector<int>> tests = {{10, 30, 5, 60}, {40, 20, 30, 10, 30}, {10, 20, 30}, {10, 20}, {5, 5, 5, 5}};
    for (auto& p : tests) {
        int c = minCost(p);
        cout << c << "  " << brackets(1, p.size() - 1) << "\n";
    }
}
4500  ((AB)C)
26000  ((A(BC))D)
6000  (AB)
0  A
250  (A(BC))

The same solution in Python

# Matrix chain multiplication: matrix i is p[i-1] x p[i]; dp[i][j] = cheapest cost to multiply matrices i..j.
def min_cost(p):
    n = len(p) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):                     # the LAST product joins (i..k) and (k+1..j)
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j], split[i][j] = cost, k

    def brackets(i, j):
        if i == j:
            return chr(ord("A") + i - 1)
        k = split[i][j]
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")"

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

for p in [[10, 30, 5, 60], [40, 20, 30, 10, 30], [10, 20, 30], [10, 20], [5, 5, 5, 5]]:
    c, b = min_cost(p)
    print(c, "", b)
4500  ((AB)C)
26000  ((A(BC))D)
6000  (AB)
0  A
250  (A(BC))

Three real bugs

Bug 1: dp[i][j] is never set to Integer.MAX_VALUE. A new int array is all zeros; no cost is smaller than 0, so the minimum never changes.

import java.util.*;

public class Main {
    static int[][] split;
    static int minCost(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n + 1][n + 1];
        split = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        return dp[1][n];
    }
    static String brackets(int i, int j) {
        if (i == j) return String.valueOf((char) ('A' + i - 1));
        int k = split[i][j];
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
    }
    public static void main(String[] args) {
        System.out.println(minCost(new int[]{40, 20, 30, 10, 30}));
    }
}
0

Bug 2: loops by start i, then end j. When i = 1, dp[k + 1][j] for later starts isn't filled yet (still 0).

import java.util.*;

public class Main {
    static int[][] split;
    static int minCost(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n + 1][n + 1];
        split = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        return dp[1][n];
    }
    static String brackets(int i, int j) {
        if (i == j) return String.valueOf((char) ('A' + i - 1));
        int k = split[i][j];
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
    }
    public static void main(String[] args) {
        System.out.println(minCost(new int[]{40, 20, 30, 10, 30}));
    }
}
20000

Bug 3: k runs up to j. With k = j the right part k+1..j is empty and reads past the table.

import java.util.*;

public class Main {
    static int[][] split;
    static int minCost(int[] p) {
        int n = p.length - 1;
        int[][] dp = new int[n + 1][n + 1];
        split = new int[n + 1][n + 1];
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; 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] + p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        return dp[1][n];
    }
    static String brackets(int i, int j) {
        if (i == j) return String.valueOf((char) ('A' + i - 1));
        int k = split[i][j];
        return "(" + brackets(i, k) + brackets(k + 1, j) + ")";
    }
    public static void main(String[] args) {
        System.out.println(minCost(new int[]{40, 20, 30, 10, 30}));
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
    at Main.minCost(Main.java:14)
    at Main.main(Main.java:29)

Complexity

Approach Time Space Big input
Cheapest pair first O(n²) O(n) fast but wrong
Every split, no memo about 3ⁿ (exponential) O(n) stack 24 matrices: Time Limit Exceeded
Interval DP O(n³) O(n²) (dp + split) 300 matrices: ~17 ms

Printing the brackets is O(n): one call per matrix and per product.

Common mistakes

Mistake What you see (real) Why Fix
Cheapest pair first 36000 instead of 26000 a cheap step forces a costly one try every last split
dp[i][j] starts at 0 0 min of 0 and any cost is 0 start at Integer.MAX_VALUE
Loop i, then j 20000, too small reads cells not filled yet loop by chain length
k <= j ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 the right part is empty k < j
Cost p[i] * p[k] * p[j] wrong totals the left part has p[i-1] rows p[i - 1] * p[k] * p[j]
int overflow on big sizes negative costs products can pass 2³¹ use long when sizes are large

Mini project: a filter-chain planner

Read the filter sizes of a camera app's chain, print the cheapest bracketing, its cost, and how many times cheaper it is than the left-to-right order (((AB)C)D).... Try a chain where the saving is more than 10×.

Practice

1. Minimum Score Triangulation of Polygon (LeetCode 1039). The triangle on edge (i, j) has a third vertex k; it splits the polygon into (i..k) and (k..j).

2. Minimum Cost Tree From Leaf Values (LeetCode 1130). Split the leaves into a left and right subtree at k; the new node costs max(left) × max(right).

3. Boolean parenthesization. Count the bracketings of an expression like T|F&T^F that make it true: for every operator k, combine (true, false) counts of both sides.

4. Fill the table for p = {5, 10, 3, 12}.

Solutions (1, 2 and 4)
import java.util.*;

public class Main {
    // Minimum Score Triangulation of Polygon (LeetCode 1039): vertices 0..n-1 in order.
    // dp[i][j] = cheapest triangulation of the polygon i..j. The triangle on edge (i, j) has a third vertex k:
    // it splits the polygon into (i..k) and (k..j), exactly like matrix chain.
    static int triangulate(int[] v) {
        int n = v.length;
        int[][] dp = new int[n][n];
        for (int len = 2; len < n; len++)
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
            }
        return dp[0][n - 1];
    }
    // Minimum Cost Tree From Leaf Values (LeetCode 1130): dp[i][j] = min over k of
    // dp[i][k] + dp[k+1][j] + max(arr[i..k]) * max(arr[k+1..j]).
    static int mctFromLeaf(int[] a) {
        int n = a.length;
        int[][] mx = new int[n][n], dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            mx[i][i] = a[i];
            for (int j = i + 1; j < n; j++) mx[i][j] = Math.max(mx[i][j - 1], a[j]);
        }
        for (int len = 2; len <= n; len++)
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + mx[i][k] * mx[k + 1][j]);
            }
        return dp[0][n - 1];
    }
    public static void main(String[] args) {
        System.out.println(triangulate(new int[]{1, 2, 3}));
        System.out.println(triangulate(new int[]{3, 7, 4, 5}));
        System.out.println(triangulate(new int[]{1, 3, 1, 4, 1, 5}));
        System.out.println(mctFromLeaf(new int[]{6, 2, 4}));
        System.out.println(mctFromLeaf(new int[]{4, 11}));
    }
}
6
144
13
32
44

For p = {5, 10, 3, 12}: AB = 150, BC = 360, ABC = min(0 + 360 + 5·10·12, 150 + 0 + 5·3·12) = min(960, 330) = 330, brackets ((AB)C).

Quick quiz

A is 5×10, B is 10×3, C is 3×12. The cheapest cost? A) 330 B) 510 C) 780 D) 1110

Answer

A) 330. (AB)C = 5·10·3 + 5·3·12 = 150 + 180 = 330; A(BC) = 10·3·12 + 5·10·12 = 360 + 600 = 960.

Interview questions

  1. What does one product cost, and why? p·q·r: p·r result cells, each a dot product of length q.
  2. Why does greedy fail? The cost of a product depends on the sizes left around it; a cheap product now can leave an expensive one for later.
  3. State and recurrence? dp[i][j] = min_k dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j], dp[i][i] = 0.
  4. Why fill by length? dp[i][j] needs shorter chains on both sides.
  5. How do you recover the brackets? Store the best k in split[i][j] and recurse.
  6. Complexity? O(n³) time, O(n²) space.
  7. How is it like burst balloons? Both choose the last step inside a range so the two sides are independent; balloons use walls (k strictly between l and r), matrices split the chain (k from i to j − 1).

Glossary

Term Meaning
Matrix A grid of numbers, rows × columns
Matrix product p × q times q × r gives p × r
Cost of a product p · q · r scalar multiplications
Associative (AB)C = A(BC): brackets don't change the result
Bracketing The order of products, written with brackets
Dimension array p[0..n]: matrix i is p[i-1] × p[i]
Sub-chain Matrices i..j in a row
Split point k: the last product joins i..k and k+1..j
Interval DP DP over ranges with a split point inside
Split table split[i][j]: the best k, used to print brackets
Greedy Taking the choice that looks cheapest right now

Summary

  • One product costs p·q·r; the bracketing can change the total work many times over.
  • Cheapest pair first is wrong; every split recursively is right but exponential.
  • The last product splits the chain into two independent parts: dp[i][j] = min_k dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j], filled by length, answer dp[1][n].
  • A split table rebuilds the brackets. O(n³) time, O(n²) space.
  • Next episode: DP on trees, house robber III, where every node returns two answers.