矩阵连乘问题(区间DP)

在算法课上遇到的问题
矩阵乘法的顺序不同，所需要计算乘法的次数也不同，如何求得1~n个矩阵乘法中，元素最小的运算次数？
如：
矩阵A为2x10的矩阵，B为10x2的矩阵，C为2x10的矩阵
1.若按照（AB)C顺序计算,需要2x2x10+2x10x2=80次乘法运算
2.若按照A(BC)顺序计算,需要10x10x2+2x10x10=400次乘法运算
可见，计算顺序不同，所需的乘法次数也不相同
分析问题：

分析可得，该问题为区间DP问题，
状态表示：
f[i][j]表示从i矩阵到j矩阵顺序相乘所需要的最少乘法次数
f[i][j]=min(f[i][k]+f[k+1][j]+这两个矩阵乘法所需要的乘法次数）
k从1到j-1
f[i][k]和f[k+1][j]这两个合并后的矩阵乘法所需要的乘法次数为：i矩阵的行数*k矩阵的列数*j矩阵的列数
1
2
3
4
5
6

关于区间DP问题可以看常见动态规划类型（线性DP、区间DP、计数DP、数位DP）
代码如下：

#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
const int inf=0x3f3f3f3f; 
int h[N],L[N];//存矩阵的行数和列数
int f[N][N];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i]>>L[i];
	
	for(int l=2;l<=n;l++)
		for(int i=1;i+l-1<=n;i++){
			f[i][i+l-1]=inf;
			for(int k=i;k<i+l-1;k++){
				f[i][i+l-1]=min(f[i][i+l-1],f[i][k]+f[k+1][i+l-1]+h[i]*L[k]*L[i+l-1]);
				}				
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			printf("%d \t",f[i][j]);
		cout<<endl;
	}
	return 0;
} 
/*
6
30 35
35 15
15 5
5 10
10 20
20 25
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

结果：
输出f[ 1 ][ n ]即可