矩阵链相乘的乘法次数（动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了矩阵链相乘的乘法次数（动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Description
设 A1, A2, …, An 为矩阵序列，Ai 是阶为 Pi − 1 * Pi 的矩阵 i = 1, 2, …, n.

试确定矩阵的乘法顺序，使得计算 A1A2…An 过程中元素相乘的总次数最少.

Input
多组数据

第一行一个整数 n(1≤n≤300) ，表示一共有 n 个矩阵.

第二行 n + 1 个整数 P0, P1, …, Pn(1≤Pi≤100) ，第i个矩阵的行数为Pi − 1，列数为Pi.

Output
对于每组数据输出最少的元素乘法次数.

Sample Input
5
74 16 58 58 88 80 
5 
10 1 50 50 20 5 
Sample Output
342848
3650

该题是算法动态规划练习题

该题首先要清楚地认识和理解题意

首先，理解一次矩阵乘法会产生多少次乘法运算

例如给定两个矩阵（10 * 5）与（5 * 20）

会产生的乘法次数为 10*5*20=1000次

然后我们要理解当存在多个矩阵相乘时，乘的顺序不同，最终乘法运算的总次数也是不同的！

到这里，我们按照动态规划的思想开始解答

我们先定义一个数组来存储子问题，这里dp[i][j]定义为矩阵[i,j]相乘的最小总次数（其中1<=i<=j<=n，n为矩阵个数）

然后就是找到子问题和子问题之间的关系（求递推方程）

很明显的是当i==j时，此时只有一个矩阵，因此乘法运算次数肯定为0

而j==i+1时，此时只有两个矩阵，因此乘法运算次数肯定为这两个矩阵的相乘乘法次数

再往上推，当有三个矩阵时，我们需要进行划分了，即划分为左边两个矩阵先乘还是右边两个矩阵先乘

因此这里我们定义一个划分变量k，定义i<=k<j，这样定义是为了方便后续计算

例如只有两个矩阵的时候，我们计算乘法次数公式就可以定义为p[i-1]*p[k]*p[j]，

然后对每一次划分的结果都进行计算乘法次数，同时取最小值不断更新我们的dp数组即可

下面给出两个版本文章来源地址https://www.toymoban.com/news/detail-822523.html
#include<cstdio>

using namespace std;

int MAX=310,inf=0x3f3f3f3f;
int n;
int p[310];
int dp[310][310];//dp[i][j]定义为矩阵[i,j]相乘的最小总次数 

int fun(int i,int j){//计算矩阵[i,j]相乘的最小总次数 (左闭右闭)
	for(int k=i;k<j;k++){//枚举划分的位置 
		int temp=fun(i,k)+fun(k+1,j)+p[i-1]*p[k]*p[j];
		if(temp<dp[i][j]){
			dp[i][j]=temp;
		}
	}
	return dp[i][j];
}

int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<=n;i++){
			scanf("%d",&p[i]);
		}
		for(int i=0;i<MAX;i++){
			for(int j=0;j<MAX;j++){
				if(i==j){
					dp[i][j]=0;
				}else{
					dp[i][j]=inf;//初始化 
				}
			}
		}
		int res=fun(1,n);
		printf("%d\n",res);
	}
	
	return 0;
} 
#include<cstdio>

using namespace std;

int MAX=310,inf=0x3f3f3f3f;
int n;
int p[310];
int dp[310][310];//dp[i][j]定义为矩阵[i,j]相乘的最小总次数 

void fun(int beg,int endd){//计算矩阵[i,j]相乘的最小总次数 (左闭右闭)
	for(int r=2;r<=n;r++){//子问题的大小 
		for(int i=1;i<=n-r+1;i++){//左边界 
			int j=i+r-1;//右边界 
			for(int k=i;k<j;k++){//枚举划分 
				int temp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
				if(temp<dp[i][j]){
					dp[i][j]=temp;
				}
			}
		}
	}
}

int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<=n;i++){
			scanf("%d",&p[i]);
		}
		for(int i=0;i<MAX;i++){
			for(int j=0;j<MAX;j++){
				if(i==j){
					dp[i][j]=0;
				}else{
					dp[i][j]=inf;//初始化 
				}
			}
		}
		fun(1,n);
		int res=dp[1][n];
		printf("%d\n",res);
	}
	
	return 0;
} 