矩阵链相乘的乘法次数动态规划

1.  
   Description
2.  
   设 A1, A2, …, An 为矩阵序列，Ai 是阶为 Pi − 1 * Pi 的矩阵 i = 1, 2, …, n.
3.  
    
4.  
   试确定矩阵的乘法顺序，使得计算 A1A2…An 过程中元素相乘的总次数最少.
5.  
    
6.  
   Input
7.  
   多组数据
8.  
    
9.  
   第一行一个整数 n(1≤n≤300) ，表示一共有 n 个矩阵.
10.  
     
11.  
    第二行 n   1 个整数 P0, P1, …, Pn(1≤Pi≤100) ，第i个矩阵的行数为Pi − 1，列数为Pi.
12.  
     
13.  
    Output
14.  
    对于每组数据输出最少的元素乘法次数.
15.  
     
16.  
    Sample Input
17.  
    5
18.  
    74 16 58 58 88 80
19.  
    5
20.  
    10 1 50 50 20 5
21.  
    Sample Output
22.  
    342848
23.  
    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数组即可

下面给出两个版本

1.  
   #include<cstdio>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   int MAX=310,inf=0x3f3f3f3f;
6.  
   int n;
7.  
   int p[310];
8.  
   int dp[310][310];//dp[i][j]定义为矩阵[i,j]相乘的最小总次数
9.  
    
10.  
    int fun(int i,int j){//计算矩阵[i,j]相乘的最小总次数 (左闭右闭)
11.  
    for(int k=i;k<j;k ){//枚举划分的位置
12.  
    int temp=fun(i,k) fun(k 1,j) p[i-1]*p[k]*p[j];
13.  
    if(temp<dp[i][j]){
14.  
    dp[i][j]=temp;
15.  
    }
16.  
    }
17.  
    return dp[i][j];
18.  
    }
19.  
     
20.  
    int main(){
21.  
    while(scanf("%d",&n)!=EOF){
22.  
    for(int i=0;i<=n;i ){
23.  
    scanf("%d",&p[i]);
24.  
    }
25.  
    for(int i=0;i<MAX;i ){
26.  
    for(int j=0;j<MAX;j ){
27.  
    if(i==j){
28.  
    dp[i][j]=0;
29.  
    }else{
30.  
    dp[i][j]=inf;//初始化
31.  
    }
32.  
    }
33.  
    }
34.  
    int res=fun(1,n);
35.  
    printf("%d\n",res);
36.  
    }
37.  
     
38.  
    return 0;
39.  
    }

1.  
   #include<cstdio>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   int MAX=310,inf=0x3f3f3f3f;
6.  
   int n;
7.  
   int p[310];
8.  
   int dp[310][310];//dp[i][j]定义为矩阵[i,j]相乘的最小总次数
9.  
    
10.  
    void fun(int beg,int endd){//计算矩阵[i,j]相乘的最小总次数 (左闭右闭)
11.  
    for(int r=2;r<=n;r ){//子问题的大小
12.  
    for(int i=1;i<=n-r 1;i ){//左边界
13.  
    int j=i r-1;//右边界
14.  
    for(int k=i;k<j;k ){//枚举划分
15.  
    int temp=dp[i][k] dp[k 1][j] p[i-1]*p[k]*p[j];
16.  
    if(temp<dp[i][j]){
17.  
    dp[i][j]=temp;
18.  
    }
19.  
    }
20.  
    }
21.  
    }
22.  
    }
23.  
     
24.  
    int main(){
25.  
    while(scanf("%d",&n)!=EOF){
26.  
    for(int i=0;i<=n;i ){
27.  
    scanf("%d",&p[i]);
28.  
    }
29.  
    for(int i=0;i<MAX;i ){
30.  
    for(int j=0;j<MAX;j ){
31.  
    if(i==j){
32.  
    dp[i][j]=0;
33.  
    }else{
34.  
    dp[i][j]=inf;//初始化
35.  
    }
36.  
    }
37.  
    }
38.  
    fun(1,n);
39.  
    int res=dp[1][n];
40.  
    printf("%d\n",res);
41.  
    }
42.  
     
43.  
    return 0;
44.  
    }

这篇好文章是转载于：学新通技术网