动态规划矩阵连乘代码

代码（1）

#include 
#define N 100
#define MAX 0xfffffff
using namespace std;
int n;
int p[N]; 
//int dp[105][105],s[105][105];dp表示当前最优值 s[][]表示切割位置 
int s[N][N],dp[N][N]; 
void MatricChain(){
    for(int i=1;i<=n;i++){  //赋初值 
        for(int j=1;j<=n;j++){
            dp[i][j]=MAX;
            s[i][j]=0;     
        }
    }
    for(int i=0;i<=n;i++){
        cin>>p[i];
        dp[i][i]=0; // 一个矩阵时不能相乘 
    }
    for(int L=2;L<=n;L++){  //
        for(int i=1;i<=n;i++){
            int j=L+i-1; 表示哪个矩阵与哪个矩阵相乘
            if(j>n) 
                break;
            for(int k=i;k<=n;k++){ //遍历切割位置
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
            }     
        }
    }
    
}

int main(){
    cin>>n;
    MatricChain();
        cout<<"连乘的最少次数是"<     
}

代码（2）

#include 
using namespace std;

#define MAX 0xfffffff
#define N 100
int n;
int p[N];
int s[N][N],dp[N][N];  //S存储切割位置，dp存储最优值 

void MatricChain(){
    for(int i=0;i         for(int j=0;j
            dp[i][j]=MAX;
            s[i][j]=0;
        }
        
    for(int i=0;i<=n;i++){
        cin>>p[i];
        dp[i][i]=0;//只有一个矩阵时不能相乘
    }
 
    for(int L=2;L<=n;L++){//相乘矩阵的个数 
        for(int i=1;i<=n;i++){ 
            int j=i+L-1;//表示哪个矩阵与哪个相乘 
            if(j>n) break; 
            for(int k=i;k                 
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
            } 
        }
    }
}

void Traceback(int i,int j){
    if(i==j) return;
    int k=s[i][j];
    Traceback(i,k);
    Traceback(k+1,j);
    cout<<"A["< }

int main()
{
    cin>>n;
    
    MatricChain();
    
     
    cout<<"连乘的最少次数是"<     //Traceback(1,n);
}