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

int recMinCost(vector<int>& D, int i, int j)
{
	if (i == j)
	{
		return 0;
	}
	else
	{
		int bestCost = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int cost = D[i - 1] * D[k] * D[j] + recMinCost(D,i, k) + recMinCost(D,k + 1, j);

			if (cost < bestCost)
				bestCost = cost;
		}
		return bestCost;
	}
}

//Run time: O(n^3)
int memoMinCost(vector<int>& D, int i, int j, int ** M)
{
	if (i == j)
	{
		return 0;
	}
	else if (M[i][j] != -1)
	{
		return M[i][j];
	}
	else
	{
		int bestCost = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int cost = D[i - 1] * D[k] * D[j] + memoMinCost(D, i, k,M) + memoMinCost(D, k + 1, j,M);

			if (cost < bestCost)
				bestCost = cost;
		}

		M[i][j] = bestCost;
		return bestCost;
	}
}

int minCost(vector<int>& D, int i, int j)
{
	int** M;
	M = new int* [D.size()];
	for (int i = 0; i < D.size(); i++)
		M[i] = new int[D.size()];

	//Initialize values in M to "not solved", -1
	for (int i = 0; i < D.size(); i++)
		for (int j = 0; j < D.size(); j++)
			M[i][j] = -1;

	return memoMinCost(D, i, j, M);
}

int main()
{
	vector<int> D = { 3,5,2,6,1,3,4,3,7,8,10,12,3,5,2,9,5,3,2,6,14,8,18,3,3,5,2,6,3,9,10,3,17,15,12,3,6,3,8,2,19,21,15,5 };
	
	//cout << recMinCost(D, 1, 3) << endl;
	cout << minCost(D, 1, 40) << endl;

	return 0;
}