#include <iostream>
#include <string>
#include <vector>
using namespace std;

//Slow (worse than exponential) time solution
//using just recursion.
int MCrec(vector<int>& D, int i, int j)
{
	if (i == j)
		return 0;
	else
	{
		int best = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int cost = MCrec(D, i, k) + MCrec(D, k + 1, j) + D[i - 1] * D[k] * D[j];
			if (cost < best)
				best = cost;
		}
		return best;
	}
}

//O(n^3) time solution using memoization
int MCmemo(vector<int>& D, int i, int j, int ** MEMO)
{
	if (i == j)
		return 0;
	if (MEMO[i][j] != -1)
		return MEMO[i][j];
	else
	{
		int best = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int cost = MCmemo(D, i, k, MEMO) + MCmemo(D, k + 1, j, MEMO) + D[i - 1] * D[k] * D[j];
			if (cost < best)
				best = cost;
		}
		MEMO[i][j] = best;
		return best;
	}
}


//return minimum matrix chain multiplicaton cost
//for matricies A_i to A_j
int MC(vector<int>& D)
{
	//create a memoization table to hold subproblem answers
	int** MEMO;
	MEMO = new int* [D.size()];
	for (int i = 0; i < D.size(); i++)
		MEMO[i] = new int[D.size()];

	//Set all subproblems to "not yet solved" (-1)
	for (int i = 0; i < D.size(); i++)
		for (int j = 0; j < D.size(); j++)
			MEMO[i][j] = -1; //represents subproblem not yet solved.
	
	return MCmemo(D, 1, D.size()-1, MEMO);
}


int main()
{
	vector<int> D0 = { 5,10,12,2}; //should be 340
	vector<int> D1 = { 5,7,3,8,6,10 };
	vector<int> D2 = { 5,7,3,8,6,10,3,5,2,9,5,3,2,5};
	vector<int> D3 = { 5,7,3,8,6,10,3,5,2,9,5,3,2,5,7,17,23,5,2};
	vector<int> D4 = { 5,7,3,8,6,10,3,5,2,9,5,3,2,5,7,17,23,5,2,5,19,21,5,7};
	vector<int> D5 = { 5,7,3,8,6,10,3,5,2,9,5,3,2,5,7,17,23,5,2,5,19,21,5,7,19,7,8,15,12,3,6,18, 7 };

	cout << MC(D5) << endl;


	return 0;
}