shu_p55 矩阵连乘问题

//shuoj P55 MatrixChain        
#include         
#include         
#include         
using namespace std;        
#define Max 24        
       
int N;        
int m[Max][Max],p[Max],s[Max][Max];        
void Traceback(int i,int j)        
{        
    if(i==j)  {cout<<"A"<>p[i];        
        for(int i=0;i<=N;i++)   m[i][i]=0;        
        if(N==1){        
            cout<<"Case "<





 
 
 
 

   
 
 
 

   
 
 
 

  分析：
 
 
 

       1.对于A[1:n]的最次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的，即具有最优子结构。所以假设对于A[i:j](1<=i<=j<=n），所需最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。动态方程如下：
 
 
 

          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 
 

       2.输出括号
 
 
 

         本题不仅要求输出m[i][j]，同时还应在输出结果中用括号来显示计算的顺序。为此在动态规划算中加入了s[][]数组，用来记录最优的断开位置。然后利用Traceback算法输出最优计算次序。由于输出样例中的最外层没有加括号，所以在Traceback函数中需要进行判断，与一般情况分开讨论。