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. A10 × 30matrix has 10 rows and 30 columns. - Matrix product: a
p × qmatrix times aq × rmatrix gives ap × rmatrix. The inner sizes must match. - Cost of one product: each of the
p · rresult cells is a row times a column,qmultiplications, sop · q · rin 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:nmatrices are described byn + 1numbers; matrixiisp[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 bestk, 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 (BCis insideABC,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²/2sub-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
- What does one product cost, and why?
p·q·r:p·rresult cells, each a dot product of lengthq. - 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.
- 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. - Why fill by length?
dp[i][j]needs shorter chains on both sides. - How do you recover the brackets? Store the best
kinsplit[i][j]and recurse. - Complexity? O(n³) time, O(n²) space.
- How is it like burst balloons? Both choose the last step inside a range so the two sides are independent; balloons use walls (
kstrictly betweenlandr), matrices split the chain (kfromitoj − 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, answerdp[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.