《算法導論》書中算法的實作,
#include<iostream>
#include<vector>
#include<limits>
using std::vector;
using std::cout;
using std::cin;
void Print_Optimal_Parens(vector<vector<int> > s,int i,int j)
{
if(i==j)
cout<<"A"<<i;
else
{
cout<<"(";
Print_Optimal_Parens(s,i,s[i-1][j-1]);
Print_Optimal_Parens(s,s[i-1][j-1]+1,j);
cout<<")";
}
}
void Matrix_Chain_order(vector<int> p,vector<vector<int> > &m,vector<vector<int> >&s)
{
int n=p.size()-1;
for(int i=1;i!=n+1;++i)
m[i-1][i-1]=0;
for(int l=2;l!=n+1;++l)
{
for(int i=1;i!=n-l+2;++i)
{
int j=i+l-1;
m[i-1][j-1]=INT_MAX;
for(int k=i;k!=j;++k)
{
int q=m[i-1][k-1]+m[k][j-1]+p[i-1]*p[k]*p[j];
if(q<m[i-1][j-1])
{
m[i-1][j-1]=q;
s[i-1][j-1]=k;
}
}
}
}
}
int main()
{
int aa[]={30,35,15,5,10,20,25};
vector<int>p(aa,aa+sizeof(aa)/sizeof(aa[0]));
int n=p.size()-1;
vector<vector<int> >m(n,vector<int>(n));
vector<vector<int> >s(n,vector<int>(n));
Matrix_Chain_order(p,m,s);
Print_Optimal_Parens(s,1,n);
cin.get();
}