看了一天的DP算法，感觉好难、、哎。、、只能继续努力了、、下面是矩阵链用c++实现的代码、、、
#include<iostream>using namespace std;pair<int*,int*> matrix(int *p,int n){ long i,l,j,k,q; int *m=new int[(n+1)*(n+1)]; int *s=new int[(n+1)*(n+1)]; for(i=0;i<=n;i++) m[i*(n+1)+i]=0; for(l=2;l<=n;l++) for(i=1;i<=n-l+1;i++) { j=i+l-1; m[i*(n+1)+j]=2100000000; for(k=i;k<=j-1;k++) { q=m[i*(n+1)+k]+m[(k+1)*(n+1)+j]+p[i-1]*p[k]*p[j]; if(q<m[i*(n+1)+j]) { m[i*(n+1)+j]=q; s[i*(n+1)+j]=k; } } } return make_pair(m,s);}void print(int *s,int i,int j,int n){ if(i==j) cout<<"A"<<i; else { cout<<"("; print(s,i,s[i*(n+1)+j],n); print(s,s[i*(n+1)+j]+1,j,n); cout<<")"; }}int main(){ int p[]={30,35,15,5,10,20,25}; int *s,*m; pair<int*,int*> r=matrix(p,6); m=r.first; s=r.second; print(s,1,6,6); cout<<endl<<m[13]<<endl; delete []s; delete []m; return 0;}
