算法导论--矩阵链相乘

#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;
}