问题背景
矩阵链乘（Matrix Chain Multiplication）是动态规划的经典入门问题。给定一系列矩阵的维度，求计算它们乘积所需的最少标量乘法次数。矩阵乘法满足结合律，但不同括号化方案的运算代价可能差异巨大。
例如，三个矩阵A(10×30)、B(30×5)、C(5×60)的链乘：
– (AB)C 需要 10×30×5 + 10×5×60 = 4500 次乘法
– A(BC) 需要 30×5×60 + 10×30×60 = 27000 次乘法
最优方案的计算量仅为次优方案的六分之一，在大型矩阵运算中这一差距会被急剧放大。
核心算法思想
区间DP状态设计
设 dp[i][j] 为计算矩阵 A_i × A_{i+1} × ... × A_j 所需的最少乘法次数。状态转移方程为：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]) (i ≤ k < j)
其中 p[i-1]×p[k] 是左半部分结果的维度，p[k]×p[j] 是右半部分结果的维度，合并需要 p[i-1]*p[k]*p[j] 次乘法。
递推顺序
按区间长度从小到大枚举，确保计算 dp[i][j] 时所有子区间 dp[i][k] 和 dp[k+1][j] 均已计算完毕。
Java完整实现
import java.util.*;
/**
* 矩阵链乘问题求解器
* 使用区间动态规划求最优括号化方案
*/
public class MatrixChainMultiplication {
private int[] dims; // 矩阵维度数组，dims[i-1]×dims[i]为第i个矩阵
private int n; // 矩阵个数
private int[][] dp; // dp[i][j]表示第i到第j个矩阵的最小代价
private int[][] split; // split[i][j]记录最优分割点k
public MatrixChainMultiplication(int[] dims) {
this.dims = dims;
this.n = dims.length - 1; // n个矩阵需要n+1个维度值
this.dp = new int[n + 1][n + 1];
this.split = new int[n + 1][n + 1];
}
/**
* 求解最优矩阵链乘方案
* @return 最小标量乘法次数
*/
public int solve() {
// 初始化：单个矩阵乘法代价为0
for (int i = 1; i <= n; i++) {
dp[i][i] = 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] = Integer.MAX_VALUE;
// 枚举分割点k：在k和k+1之间分割
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;
split[i][j] = k;
}
}
}
}
return dp[1][n];
}
/**
* 递归构造最优括号化方案
*/
public String getOptimalParenthesization(int i, int j) {
if (i == j) {
return "A" + i;
}
int k = split[i][j];
String left = getOptimalParenthesization(i, k);
String right = getOptimalParenthesization(k + 1, j);
return "(" + left + " × " + right + ")";
}
/**
* 打印DP表用于调试
*/
public void printDPTable() {
System.out.println("DP表（最小乘法次数）:");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j < i) {
System.out.printf("%8s ", "-");
} else {
System.out.printf("%8d ", dp[i][j]);
}
}
System.out.println();
}
}
/**
* 迭代版本的矩阵链乘（基于自底向上DP）
* 与solve()逻辑一致，显式展示递推过程
*/
public int solveIterative() {
// dp[i][j]已自动初始化为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] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int q = dp[i][k] + dp[k + 1][j]
+ dims[i - 1] * dims[k] * dims[j];
if (q < dp[i][j]) {
dp[i][j] = q;
split[i][j] = k;
}
}
}
}
return dp[1][n];
}
public static void main(String[] args) {
// 示例：6个矩阵，维度分别为 30×35, 35×15, 15×5, 5×10, 10×20, 20×25
int[] dims = {30, 35, 15, 5, 10, 20, 25};
MatrixChainMultiplication mcm = new MatrixChainMultiplication(dims);
int minCost = mcm.solve();
System.out.println("最小标量乘法次数: " + minCost);
System.out.println("最优括号化方案: " + mcm.getOptimalParenthesization(1, 6));
mcm.printDPTable();
// 对比示例：A(10×30), B(30×5), C(5×60)
int[] dims2 = {10, 30, 5, 60};
MatrixChainMultiplication mcm2 = new MatrixChainMultiplication(dims2);
int minCost2 = mcm2.solve();
System.out.println("\n示例2 最小乘法次数: " + minCost2);
System.out.println("示例2 最优方案: " + mcm2.getOptimalParenthesization(1, 3));
// (AB)C = 10*30*5 + 10*5*60 = 1500 + 3000 = 4500
// A(BC) = 30*5*60 + 10*30*60 = 9000 + 18000 = 27000
}
}
算法复杂度分析
- 状态数量：
O(n²)，共有n(n+1)/2个区间状态 - 状态转移：每个状态枚举分割点
k，O(n) - 总时间复杂度：
O(n³) - 空间复杂度：
O(n²)，用于存储dp表和分割点表
对于大规模矩阵链（n > 200），O(n³) 的复杂度可能较高。此时可考虑：
– Knuth优化：若满足四边形不等式，可将复杂度降至 O(n²)
– 并行计算：不同区间长度的计算可部分并行化
算法扩展与变种
最优二叉搜索树
矩阵链乘与最优二叉搜索树（OBST）的DP结构高度相似，均采用区间DP框架。OBST的期望搜索代价最小化可以看作带权版本的矩阵链乘问题。
多边形三角剖分
凸多边形的最优三角剖分同样可转化为区间DP，与矩阵链乘同构。每个三角剖分方案对应一种矩阵链乘的括号化方案。
记忆化搜索实现
区间DP也可采用自顶向下的记忆化搜索实现，代码更直观但常数稍大：
public int memoSolve(int i, int j) {
if (i == j) return 0;
if (dp[i][j] != -1) return dp[i][j];
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = memoSolve(i, k) + memoSolve(k + 1, j)
+ dims[i-1] * dims[k] * dims[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
return dp[i][j];
}
区间DP的核心在于”大事化小”：将大区间最优解分解为小区间最优解的组合。掌握这一思想后，大量看似复杂的问题都能被优雅地解决。
