使用动态规划方法,n个矩阵相乘有以下递归性质： M[i][j]=min(i<=k<=j−1)(M[i][k]+M[k+1][j]+di−1dkdj) (if i<j) M[i][j]=0
#include<iostream> #include<stdio.h> #include<stdlib.h> #include <string.h> #include<algorithm> using namespace std; //矩阵链乘法求两矩阵相乘所需的最小次数，以及数组P的作用是在哪个地方进行分割。 int P[15][15];//P[i][j]为从矩阵i乘到矩阵j在哪儿划分最好 int M[19][19]; //算法3.6最小量乘法 int minmult(int n,const int d[])//n为几个矩阵相乘，d为维度， { int i,j,k,diagonal; for(i=1;i<=n;i++) M[i][i]=0; for(diagonal=1;diagonal<=n-1;diagonal++)//对角线1刚刚高于主对角线 { for(i=1;i<=n-diagonal;i++) { j=i+diagonal; M[i][j]=M[i][i]+M[i+1][j]+d[i-1]*d[i]*d[j];//首先给M一个初始值，在下面求min的时候也好有个比较。 P[i][j]=i;//同样需要提前赋值，不然下面if不成立的话，P[i][j]就空了。 for(k=i+1;k<=j-1;k++) { int temp=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]; if(temp<M[i][j]) { M[i][j]=temp; P[i][j]=k; } } } } return M[1][n]; } //输出最优顺序 算法3.7 void order(int i,int j) { if(i==j) cout<<"A"<<i; else{ int k=P[i][j]; cout<<"("; order(i,k); order(k+1,j); cout<<")"; } } main() { memset(M,0,sizeof(int)); memset(P,0,sizeof(int)); int n=6; int d[8]={5,2,3,4,6,7,8};//需要注意一下，，d数组的范围是从0开始 int sum=minmult(n,d); cout<<"输出数组P"<<endl; for(int i=1;i<n;i++) { for(int j=1;j<=n;j++) cout<<P[i][j]<<" "; cout<<endl; } cout<<endl; cout<<"输出数组M"<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<M[i][j]<<" "; cout<<endl; } cout<<endl; cout<<endl<<"最少数量："<<sum<<endl<<endl; order(1,n); cout<<endl; return 0; }