算法导论--矩阵链相乘

#include<iostream>
using namespace std;
/*
计算括号化方案数:标量乘法作为代价衡量，应该使标量乘法尽可能少。
m[i,j]表示Ai.....Aj所需标量乘法的最小值。
i=j 时只有一个矩阵，无需分割  m[i,i]=0;
采用自底向上的方式：
*/
int m[100][100];
int p[]={30,35,15,5,10,20,25};
int bottomcut(int n){
    int t;
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){    //i<=n-l+1   防止后面的j超出n
            int j=i+l-1;
            m[i][j]=100000;
            for(int k=i;k<j;k++){
                t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(t<m[i][j])
                        m[i][j]=t;
            }
            
        }
    }
    return 0;
}


int main(){
    int n;
    while(cin>>n){
    memset(m,0,sizeof(m));
    bottomcut(n);
    cout<<m[1][n]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<m[i][j]<<" ";
        }
        cout<<endl;
     }
    }
    
    return 0;
}

加入打印信息

#include<iostream>
using namespace std;
int m[100][100];
int s[100][100];
int p[]={3,2,5,10,2,3};
int bottomcut(int n){
    int j,i,k,l,min;
    for( l=1;l<=n;l++){
        for(i=1;i<=n-l;i++){
            j=i+l;
            m[i][j]=10000;
            for(k=i;k<j;k++){
                min=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(m[i][j]>min){
                    m[i][j]=min;
                    s[i][j]=k;
                }
        }
        }
    }
    return 0;
}

void Traceback(int i,int j){
    if(i==j)  return;
    Traceback(i,s[i][j]);
    Traceback(s[i][j]+1,j);
    cout<<"A["<<i<<":"<<s[i][j]<<"]"<<"乘以"<<"A:"<<(s[i][j]+1)<<"[:"<<j<<"]"<<endl;
}
int main(){
    int n;
    
    while(cin>>n){
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    bottomcut(n);
    cout<<m[1][n]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<m[i][j]<<"   ";
        }
        cout<<endl;
     }
    Traceback(1,n);
    }
    
    return 0;
}