一.问题描述
与分治法不同的是动归的子问题间不是相互独立的,前一个往往为后一个提供信息。
看下面一个例子,计算三个矩阵连乘{A1,A2,A3};维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数((A1*A2)*A3):10X100X5+10X5X50=7500次 按此顺序计算需要的次数(A1*(A2*A3)):10X5X50+10X100X50=75000次
所以问题是:如何确定运算顺序,可以使计算量达到最小化。
二.问题分析
枚举显然不可,如果枚举的话,相当于一个“完全加括号问题”,次数为卡特兰数,卡特兰数指数增长,必然不行。
令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。 显然如果i=j,则m[i][j]这段中就一个矩阵,需要计算的次数为0;如果i>j,则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j之间游荡,所以i<=k<j ;
注意的问题:计算顺序!!! 因为你要保证在计算m[i][j]查找m[i][k]和m[k+1][j]的时候,m[i][k]和m[k+1][j]已经计算出来了。
下面采用记忆化搜索实现。
三.程序实现
1 #include2 using namespace std; 3 const int N = 105; 4 int c[N][N],s[N][N],p[N]; 5 6 //根据s[][]记录的各个子段的最优解,将其输出 7 void traceback(int i,int j) 8 { 9 if(i==j)10 return ;11 traceback(i,s[i][j]);12 traceback(s[i][j]+1,j);13 cout<<"Multiply A"< <<","< <<"and A"<<<","<< 0)19 return c[i][j]; 20 if(i==j)21 return 0; 22 //初始化 23 int u=chain(i,i)+chain(i+1,j)+p[i-1]*p[i]*p[j]; 24 s[i][j]=i; 25 for(int k=i+1;k >n; 43 for(i=0;i<=n;i++) 44 cin>>p[i]; 45 cout< <