题意：

计算$A_0A_1A2....A_n$矩阵连乘需要的最少计算量。
$A_{p*q}$与$B_{q*r}$相乘计算量为$p*q*r$

分析：

状态表示——集合$F[i][j]$： 矩阵$A_i....A_j$的连乘数。
状态表示——属性$F[i][j]$： 矩阵$A_i....A_j$的连乘乘积数最小值

当$i=j$时，$F[i][j]$相当于一个矩阵$A_i$，故此时$F[i][j]=0$

当$i<j$时，假设$F[i][j]$的最优次序在$A_k$和$A_{k+1}$断开，故有$F[i][j]=f[i][k]+f[k+1][j]+P_{i-1}P_kP_j$
其中$P$数组为矩阵$A_{ij}$的维数。

最后的答案即$F[1][n]$

时间复杂度： $O(n^3)$

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 105;

int n;
int p[105];
int f[105][105];

void dp() {
	for(int i = 1; i <= n; i ++)	f[i][i] = 0;
	for (int len = 2; len <= n; len ++) { //枚举长度 
		for (int i = 1; i <= n - len + 1; i ++) { // 起点 
			int j = i + len - 1;
			f[i][j] = f[i][i] + f[i + 1][j] + p[i - 1] * p[i] * p[j];
			for (int k = i + 1; k < j; k ++) { // 枚举分界点 
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + p[i - 1] * p[k] * p[j]);
			}
		}
	}
}

int main() {

	scanf("%d", &n);
	for (int i = 0; i <= n; i ++) {
		scanf("%d", &p[i]);
	}
	dp();
	printf("%d\n", f[1][n]); 
	return 0;
} 

题目链接：矩阵连乘

Q.E.D.