Matrix Chain Multiplication
In this page:
Problem Idea
When multiplying a chain of matrices together, the total number of scalar multiplications needed depends heavily on the order you group the multiplications in — this problem finds the grouping (parenthesization) that minimizes that total cost.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
int dims[] = {10, 20, 30, 40};
cout << "3 matrices chained -- grouping order changes total scalar multiplications needed";
return 0;
}public class Main {
public static void main(String[] args) {
int[] dims = {10, 20, 30, 40};
System.out.println("3 matrices chained -- grouping order changes total scalar multiplications needed");
}
}dims = [10, 20, 30, 40]
print("3 matrices chained -- grouping order changes total scalar multiplications needed")#include <stdio.h>
int main() {
int dims[] = {10, 20, 30, 40};
printf("3 matrices chained -- grouping order changes total scalar multiplications needed");
return 0;
}Login to try C/C++/Java code in the editor
Cost Formula
Multiplying a p×q matrix by a q×r matrix costs exactly p × q × r individual multiplications, so every possible way of splitting the chain has a computable cost, and the goal is to find the split that adds up to the smallest total.
Example: Cost Formula
#include <iostream>
using namespace std;
int main() {
int p = 10, q = 20, r = 30;
cout << "Multiplying " << p << "x" << q << " by " << q << "x" << r << " costs " << p*q*r << " multiplications";
return 0;
}public class Main {
public static void main(String[] args) {
int p = 10, q = 20, r = 30;
System.out.println("Multiplying " + p + "x" + q + " by " + q + "x" + r + " costs " + (p*q*r) + " multiplications");
}
}p, q, r = 10, 20, 30
print(f"Multiplying {p}x{q} by {q}x{r} costs {p*q*r} multiplications")#include <stdio.h>
int main() {
int p = 10, q = 20, r = 30;
printf("Multiplying %dx%d by %dx%d costs %d multiplications", p, q, q, r, p*q*r);
return 0;
}Login to try C/C++/Java code in the editor
DP State
dp[i][j] stores the minimum cost of multiplying the contiguous run of matrices from index i through index j, so smaller ranges are solved first and combined to answer larger ranges.
Example: DP State
#include <iostream>
using namespace std;
int main() {
int dp[4][4] = {0};
cout << "dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] dp = new int[4][4];
System.out.println("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger");
}
}dp = [[0]*4 for _ in range(4)]
print("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger")#include <stdio.h>
int main() {
int dp[4][4] = {0};
printf("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger");
return 0;
}Login to try C/C++/Java code in the editor
Optimal Split
For a given range of matrices, the algorithm tries every possible point to split it into a left group and a right group, computes the cost of each split (left cost + right cost + cost to multiply the two resulting matrices together), and keeps the cheapest.
Example: Optimal Split
#include <iostream>
using namespace std;
int main() {
int dims[] = {10,20,30,40};
int n = 3;
int dp[4][4] = {0};
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n-len+1; i++) {
int j = i+len-1;
dp[i][j] = 1000000000;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
dp[i][j] = min(dp[i][j], cost);
}
}
cout << "Minimum total cost: " << dp[1][n];
return 0;
}public class Main {
public static void main(String[] args) {
int[] dims = {10,20,30,40};
int n = 3;
int[][] dp = new int[4][4];
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n-len+1; i++) {
int j = i+len-1;
dp[i][j] = 1000000000;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
System.out.println("Minimum total cost: " + dp[1][n]);
}
}dims = [10,20,30,40]
n = 3
dp = [[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):
cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]
dp[i][j] = min(dp[i][j], cost)
print("Minimum total cost:", dp[1][n])#include <stdio.h>
int main() {
int dims[] = {10,20,30,40};
int n = 3;
int dp[4][4] = {0};
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n-len+1; i++) {
int j = i+len-1;
dp[i][j] = 1000000000;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
if (cost < dp[i][j]) dp[i][j] = cost;
}
}
printf("Minimum total cost: %d", dp[1][n]);
return 0;
}Login to try C/C++/Java code in the editor
Practice
This is a textbook example of interval DP, where the subproblems are defined over contiguous ranges [i, j] rather than prefixes — the same pattern reappears in problems like optimal polygon triangulation and burst-balloon-style puzzles.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation");
}
}print("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation")#include <stdio.h>
int main() {
printf("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: