practice2.1.cpp

1． Matrix-chain product. The following are some instances a) <3, 5, 2, 1,10> b) <2, 7, 3,

#include <iostream>
#include <limits> 
using namespace std;

int m[100][100];
int s[100][100];

void matrix_chain_order(int p[])
{
	int i,j,k,l,q;
	int n = sizeof(p)/sizeof(*p);
	for(i = 1;i <= n;i++)
	{
		m[i][i] = 0;
	}
	for(l = 2;l <= n;l++)
	{
		for(i = 1;i <= n-l+1;i++)
		{
			j = i+l-1;
			m[i][j] =  numeric_limits<int>::max(); 
			for(k = i;k <= j-1;k++)
			{
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if(q < m[i][j])
				{
					m[i][j] = q;
					s[i][j] = k;
				}
			}
		}
	}
}

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

int main()
{
	int p[] = {0,3, 5, 2, 1,10};
    matrix_chain_order(p);
    print_optimal_parens(1,5);
	return 0;
}