最优矩阵链乘 - JAVA - 编程开发网

#include #include using namespace std; int a[101][101], b[101], sum = 0; int c[101][101], d[101][2]; const int INF = 1e9; int GetMuls(int n, int m) { if(n==m) return 0; if(a[n][m]>0) return a[n][m]; sum++; int num = INF; int tmp = INF; for(int i=n;i 0) { //在不止一个矩阵的情况下才加括号，防止单个矩阵直接被括号包围 d[n][0]++; //第n个空隙处左括号数量加1 d[i+1][1]++; //第i + 1个空隙处右括号数量加1 } if(m-i-1>0) { //在不止一个矩阵的情况下才加括号，防止单个矩阵直接被括号包围 d[i+1][0]++; //第i + 1个空隙处左括号数量加1 d[m+1][1]++; //第m + 1个空隙处右括号数量加1 } Solve(n,i); //计算n到i的括号数量及位置 Solve(i+1,m); //计算i + 1到m的括号数量及位置 } int main() { int t,i,j; //freopen("d:\\test.txt","r",stdin); while(cin>>t&&t) { for(i=0;i >b[i]>>b[i+1]; } for(i=0;i<=100;i++) { for(j=0;j<=100;j++) { a[i][j]=0; c[i][j]=0; } d[i][0]=0; d[i][1]=0; } cout< 1&&i

测试案例输出结果：

                                    
                                     7500
                                     (A1*A2)*A3
                                     15125
                                     (A1*(A2*A3))*((A4*A5)*A6)

最优矩阵链乘(二)