CPP

matrix chainmultiplication

#include <bits/stdc++.h>
using namespace std;
int MatrixChainOrder(int p[], int n)
{
	int m[n][n],s[n][n];

	int i, j, k, L, q;

	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] = 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;
				}
			}
		}
	}
	cout<<endl<<endl;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(i<=j) 
            cout<<m[i][j]<<"	";
            else
            cout<<"-1	";
            
        }
        cout<<endl;
    }
    cout << "Minimum number of multiplications is ";
	return m[1][n - 1];
}
int main()
{
	int arr[] = { 4,45,3,2,7,5 };
	int size = sizeof(arr) / sizeof(arr[0]);
	cout <<MatrixChainOrder(arr, size);
	getchar();
	return 0;
}