可以用加括号的方式来确定。例如，矩阵连乘积A1A2A3A4可以有5种不同的完全加括号方式：
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p*q的矩阵， B是一个q*r的
矩阵，其乘机C=AB是一个p*r的矩阵，总共需要pqr次数乘。
为了说明在计算矩阵连乘积
时，加括号方式对整个计算量的影响，我们考察计算3个矩阵A1A2A3的连乘积的例子。
这3个矩阵的尺寸分别为10*100，100*5和5*50。 若以((A1A2)A3)这种方式计算，
3个矩阵的连乘积需要的数乘次数为7500。 若以(A1(A2A3))这种方式计算，
所需的数乘次数为75000。显然，在即算矩阵连乘积时，加括号方式对计算量有很大影响。
1.分析最优解的结构
设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征。我们将矩阵连乘积AiAi+1....Aj简记为A[ i : j ]。考察计算A[ 1: n]的最优计算次序。设这个计算
次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n，则其相应的完全加括号形式为((A1...Ak)
(Ak+1...An))。以此次序，总的计算量为A[ 1 : k ]的计算量加上A[ k+1 : n ]的计算量，
再加上A[ 1 : k ]和A[ k+1 : n ]相乘的计算量。
这个问题的关键特征是：计算A[ 1 :n ]的最优次序所包含的计算矩阵子链a[ 1 : k ]和
A[ k+1 : n ]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的
最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可以用动态规划算法
求解的显著特征。
2.建立递归关系
设计动态规划算法的第二步就是递归地定义最优值。对于矩阵连乘积的最有计算次序问题，设计算A[ i : j ], 1<=i<=j<=n，所需的最少数乘次数为m[ i ][ j ]，则原问题的最优
值为m[ 1 ][ n]。 当i=j 时，A[ i ; j ]=Ai，为单一矩阵，无需计算，因此m[ i ][ i ]=0。
当i < j 时，可以利用最优子结构的性质来计算m[ i ][ j ]。事实上，若计算A[ i : j
]的最优次序在Ak和Ak+1之间断开，i<=k<j，则m[ i ][ j ]=m[ i ][ k ]+m[k+1][ j ]
+Pi-1*Pk*Pj。其中Pi表示第i个矩阵的列数，也是第i-1个矩阵的行数，P0表示第一个矩阵的
行数。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。从
而m[ i ][ j ]可以递归地定义为
当i<j m[ i ][ j ] = min{ m[ i ][ k ]+m[ k+1 ][ j ]+P(i-1)*Pk*Pj }
m[ i ][ j ]给出了最优值，即计算A[ i : j ]所需的最少数乘次数。同时还确定了计算
A[ i : j ]的最优次序中的断开位置k，也就是说，对于这个k有
m[ i ][ j ]=m[ i] [ k ]+m[ k+1 ][ j] + P(i-1)*Pk*Pj
若将对应于m[ i ][ j ]的断开位置k记为s[ i ][ j ]， 在计算最优值m[ i ][ j ]后
，可以递归地有s[ i ][ j ]构造出相应的最优解。
3.计算最优值
根据计算m[ i ][ j ]的递归式，容易写一个递归算法计算m[ 1 ][ n ]。但是简单地递归将好费指数计算时间。在递归计算时，许多子问题被重复计算多次。这也是该问题可以用动
态规划算法求解的又一显著特征。
用动态规划算法解决此问题，可依据其递归是以自底向上的方式进行计算。在计算的过程
中，保存以解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从
而避免大量的重复计算。
#include<iostream>
using namespace std;
const int LEN = 50;
int p[LEN]; //p用来记录矩阵的行列，main函数中有说明
int m[LEN][LEN]; //m[i][j]用来记录第i个矩阵至第j个矩阵的最优解
int s[LEN][LEN]; //s[i][j]: 从i到j的连乘子串，从s[i][j]位置处断开能得到最优解
int N;//矩阵个数
void matrixChain(){
for(int i=1;i<=N;i++)//连乘长度为1时保证为0，此为边界条件。
m[i][i]=0;
for(int r=2;r<=N;r++)//连乘长度
for(int i=1;i<=N-r+1;i++){//行循环
int j = r+i-1;//列的控制:m[i][j]表示长度为r的连乘对，显然连乘长度从2到n。
//找m[i][j]的最小值，首先假设最优解为从i节点断开
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
//k表示断开位置，从[i+1,j)，循环找m[i][j]的最小值
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;
}
}
}
}
//根据s[][]记录的各个子段的最优解，将其输出
void traceback(int i,int j, int s[][LEN]){
if(i == j){
cout<<"A"<<i;
}else if(i+1 == j){
cout<<"(A"<<i<<"A"<<j<<")";
}else{
cout<<"(";
traceback(i,s[i][j],s);
traceback(s[i][j]+1,j,s);
cout<<")";
}
}
int main(){
cout<<"矩阵个数:"<<endl;
cin>>N;
cout<<"输入矩阵A1维数"<<"：";
cin>>p[0]>>p[1];
for(int i=2 ; i<=N ; i++){
int t = p[i-1];
cout<<"输入矩阵A"<<i<<"维数：";
cin>>p[i-1]>>p[i];
if(p[i-1] != t){
cout<<endl<<"维数不对，矩阵不可乘！"<<endl;
exit(1);
}
//cout<<endl;
}
matrixChain();
cout<<endl<<"最优组合为："<<endl;
traceback(1,N,s);
cout<<endl<<"最优值为："<<m[1][N]<<endl<<endl;
return 0;
}
/*
3
100 5
5 200
200 3
*/