matrix chain multiplication c++ code

matrix-chain-multiply.cpp

#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>

using namespace std;

int min(int a, int b);
int matrixChainMultiply(vector <int> dimension);

int main(void)
{
	cout << "enter number of matrices" << endl;
	int n = 0;
	cin >> n;

	vector <int> matrix(n + 1);

	cout << "enter " << n + 1 << " numbers indicating the dimansions of the matrices.\ninput example:\nn = 4\n1 2 3 4 5\nwhich means 4 matrices with 1 * 2, 2 * 3, 3 * 4, 4 * 5 dimensions" << endl;
	for (int i = 0; i <= n; ++i)
		cin >> matrix[i];

	int result = matrixChainMultiply(matrix);
	cout << result << endl;

	return 0;
}


int matrixChainMultiply(vector <int> dimension)
{
	int n = dimension.size() - 1;
	vector < vector <int> > arr(n + 1, vector <int> (n + 1));
	
	for (int i = 0; i < n; ++i)
		arr[i][i] = 0;

	for (int l = 2; l <= n; ++l)
		for (int i = 1; i <= n - l + 1; ++i){
			int j = i + l - 1;

			arr[i][j] = INT_MAX;
			for (int k = i; k < j; ++k)
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k + 1][j] + dimension[i - 1] * dimension[k] * dimension[j]);


		}
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= n; ++j)
			cout << setw(7) << arr[i][j] << ' ';
		cout << endl;
	}

	return arr[1][n];
}


int min(int a, int b)
{
	return a > b ? b : a;
}