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


//Using normal recursion:  more than exponential in n= j-i+1.
int recC(vector<int>& A, int i, int j)
{
	if (i == j)
		return 0;
	else
	{
		int smallestSoFar = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int val = recC(A,i,k) + A[i-1]*A[k]*A[j] + recC(A,k+1,j);
			if (val < smallestSoFar)
				smallestSoFar = val;
		}
		return smallestSoFar;
	}
}

//Memoization approach:  O(n^3), where n is j-i+1.
int memoC(vector<int>& A, int i, int j, int ** M)
{
	if (i == j)
		return 0;
	else if (M[i][j] != -1)
		return M[i][j];
	else
	{
		int smallestSoFar = INT_MAX;
		for (int k = i; k < j; k++)
		{
			int val = memoC(A, i, k,M) + A[i - 1] * A[k] * A[j] + memoC(A, k + 1, j,M);
			if (val < smallestSoFar)
				smallestSoFar = val;
		}
		M[i][j] = smallestSoFar;
		return smallestSoFar;
	}
}

//Compute the cost of the minimum cost order to multiply
//a chain of n matrices with given sequence
//of dimensions A.
int minCost(vector<int>& A)
{
	int n = A.size()-1;
	
	//Create dynamic programming/memoization table
	int** M;
	M = new int* [n + 1];
	for (int i = 0; i <= n; i++)
		M[i] = new int[n + 1];

	//Initialize entries in table to "not yet computed"
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			M[i][j] = -1;

	return memoC(A, 1, n, M);
	//return recC(A, 1, n);

	//Delete/free table M (not implemented)
}

int main()
{
	vector<int> numsTest{ 5,7,30,9 }; //answer 2205
	vector<int> nums0{ 3,12,6,15 }; //answer: 486
	vector<int> nums1{ 5,8,2,4 };
	vector<int> nums2{ 5,10,4,7,5,2,9,8,4,2,6,2 };
	vector<int> nums3{ 15, 3, 6, 8, 53, 12, 35, 23, 2, 12, 8, 7, 8, 2, 4, 9, 8, 7, 4, 2, 3, 5, 3, 6 };
	vector<int> nums4{ 15, 3, 6, 8, 53, 12, 35, 23, 2, 12, 8, 7, 8, 2, 4, 9, 8, 7, 4, 2, 3, 5, 3, 6,12,5,7,6,10,9,13,12,50 };

	cout << minCost(numsTest) << endl; //2205
	cout << minCost(nums0) << endl; //486
	cout << minCost(nums2) << endl; //?
	cout << minCost(nums3) << endl;
	cout << minCost(nums4) << endl;

	return 0;
}