借鉴了别人的程序，有个疑惑为什么i从1开始不从0开始
#include <iostream>
#include <iomanip>
using namespace std;
void functionD(int *p,int n,int **m,int **s) {
for (int i=1 ; i <= n; i++){
m[i][i]=0;//将单个矩阵相乘的次数设为0
}
for(int r=2 ; r <= n; r++) {//r为矩阵链的规模
for(int i=1; i<=n-r+1;i++){//i为前边界
int j=i+r-1;//j为后边界
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];//记录断点在i处时所需要的乘法次数
s[i][j]=i;//将断点初始化在i处
for(int k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];/*实现重叠子问题的利用*/
if(t<m[i][j]) {//如果新的断点的乘法次数小于原来的次数
m[i][j]=t;//更新最少乘法次数
s[i][j]=k;//保存最佳断点位置
}
}
}
}
}
int main(){
int p[] = {5,4,3,12,5,50};//矩阵链的行列数
int n=(sizeof(p)/sizeof(p[0]))-1;//矩阵的个数
int **m,**s;
m=new int *[n+1];
for(int i=0;i<n+1;i++){
m[i]=new int [n+1];
}
s=new int *[n+1];
for(int i=0;i<n+1;i++){
s[i]=new int [n+1];
}
functionD(p,n,m,s);
cout<<" ";
for(int i=1;i<=n;i++){
cout<<setw(8)<<i;
}
cout<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(j==0) cout<<i;
else if(j<i) cout<<setw(8)<<" ";
else cout<<setw(8)<<m[i][j];
}
cout<<endl;
}
cout<<endl;
cout<<" ";
for(int i=1;i<=n;i++){
cout<<setw(8)<<i;
}
cout<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(j==0) cout<<i;
else if(j<=i) cout<<setw(8)<<" ";
else cout<<setw(8)<<s[i][j];
}
cout<<endl;
}
return 0;
}
