矩阵乘法有两个需要注意的地方，第一个就是A*B时，A的列数要个B的行数相同，另外一个需要注意的地方就是矩阵乘法不满足交换律。
在矩阵中有维度，而矩阵连乘就是维度相乘，例如：A的矩阵维度是5*10,B的矩阵是10*10，那么相乘的次数就是5*10*10，在多矩阵乘法当中可以使用（）来改变乘法的次数，这种方法可以使用穷举法，可是在少矩阵中还是可以的，如果特别多的情况之下，就会特别的耗费时间，那么可以采用动态规划方法来解决。下面来简要介绍一下动态规划的要素，以及步骤。基本要素：1，最优子结构性质2，重叠子问题性质。步骤：1，找出最优解的性质，并刻画结构特征2，递归定义最优解3，以自底而上的方式计算最优解4，根据最优解时得到的信息构造最优解。
下面对矩阵连乘进行分析，因为要对其加括号来改变优先级，所以在子问题当中也应该是最优解的形式，所以计算次序的最优解 应该包含着子问题的最优解。下面就来建立递归关系m[i][j]=0(i==j ) m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}(i<j) 计算最优解，在计算之中需要计算重复的计算，就会增加时间复杂度，所以可以使用一个函数来记录计算结果
#include <iostream> #include <stdio.h> using namespace std; void matrixChain(int *p,int m[][100],int s[][100],int n) { for(int i=0;i<=n;i++) m[i][i]=0; for(int r=2;r<=n;r++)//矩阵相乘的个数 for(int i=1;i<=n-r+1;i++)//矩阵开始位置 { int j=i+r-1;//矩阵结束位置 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i;//断点位置 for(int k=i+1;k<j;k++)//截断位置 {int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t<m[i][j]){m[i][j]=t;s[i][j]=k;} } } } void trackback(int i,int j,int s[][100]) { if(i==j) return ; trackback(i,s[i][j],s); trackback(s[i][j]+1,j,s); cout<<"Mutiply A"<<i<<","<<s[i][j]; cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl; } int main() { int p[100],m[100][100],s[100][100]; int n; cin>>n; for(int i=1;i<=n;i++) cin>>p[i]; matrixChain(p,m,s,n); trackback(1,n,s); return 0; }
