历届试题 矩阵乘法

Posted on | In |

问题描述
　　有n个矩阵，大小分别为a0a1, a1a2, a2a3, …, a[n-1]a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。

　　两个大小分别为pq和qr的矩阵相乘时的运算次数计为pqr。
输入格式
　　输入的第一行包含一个整数n，表示矩阵的个数。
　　第二行包含n+1个数，表示给定的矩阵。
输出格式
　　输出一个整数，表示最少的运算次数。
样例输入
3
1 10 5 20
样例输出
150
数据规模和约定
　　1<=n<=1000, 1<=ai<=10000。

类似于合并石子问题

子问题：矩阵i到j合并最小花费

确实是一个区间dp,但是我当时写的时候也有点乱,n个矩阵给你n+1个数,那么dp[1][n]就表示从第1个矩阵合并到第n个矩阵的最小花费。我们首先观察给你n+1个数,a[i]为其行数,a[i+1]为其列数,并且对于两个矩阵 p q q r 合并 则合并完后为p r. 花费为pqr; 也就是说对于(i,j)找到一个中间态的矩阵k,合并之后的花费为 a[i]a[k+1]a[j+1]；（这是因为如果将i k两个矩阵合并后的话变为 a[i]a[k+1]的矩阵了 （第k个矩阵的列为a[k+1]）） 

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
#include<iostream>
#include<cstring>
#include<cmath>
typedef long long ll;
#define inf (ll) 1<<62
#define MAX 1001
using namespace std;

int n;
ll dp[MAX][MAX];
ll num[MAX];
ll min(ll a,ll b)
{
    return a>b?b:a;
}
int main(){
	//cin>>n;
	scanf("%d",&n);
	   memset(dp,0,sizeof(dp));
	for(int i=1;i<=n+1;i++)
	scanf("%lld",&num[i]);
	 
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
		int j=i+len-1;		//!!
		dp[i][j]=inf;
		for(int k=i;k<j;k++)
		
		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+num[i]*num[k+1]*num[j+1]);
	}
}
	
printf("%lld\n",dp[1][n]);
    return 0;

	
}

错误代码

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
#include<iostream>
using namespace std;
#define MAX 105
int n;
int mod=1000000007;
long long dp[MAX][MAX];
int num[MAX];
int main(){
	fill(dp[0],dp[0]+MAX*MAX,0x3f3f3f);
	cin>>n;
	for(int i=0;i<n+1;i++)
	cin>>num[i];
	for(int i=0;i<n;i++){
			dp[i][i+1]=num[i]*num[i+1];
		if(i!=n-1)dp[i][i+2]=num[i]*num[i+1]*num[i+2];
	}
	for(int i=0;i<n+1;i++){
		for(int j=i+1;j<n+1;j++){
			for(int k=i+1;k<j;k++)
			{
				if(dp[i][j]>dp[i][k]+dp[k][j])
				dp[i][j]=dp[i][k]+dp[k][j];
			}
			
		}
	}
	
	
	cout<<dp[0][n];
	
	
}

参考链接
https://blog.csdn.net/sinat_35637319/article/details/55253915