// https://www.geeksforgeeks.org/optimal-binary-search-tree-dp-24/
// C++ program for recursive implementation of optimal binary search tree
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

const int Infini = numeric_limits<int>::max();

// A utility function to get sum of array elements freq[i] to freq[j]
int sum(vector<int> &freq, int i, int j)
{
	int s = 0;
	for(int k = i; k <= j; k++)
		s += freq[k];

	return s;
} // sum()

// A recursive function to calculate cost of optimal binary search tree
int optCost(vector<int> &freq, int i, int j)
{
	// No elements in this subarray
	if(j < i)
		return 0;

	// One element in this subarray
	if(j == i)
		return freq[i];

	// Get sum of freq[i], freq[i+1], ... freq[j]
	int fsum = sum(freq, i, j);

	// Initialize minimum value
	int minimum = Infini;

	// One by one consider all elements r = i, ..., j as root and recursively find cost
	// of the BST. Compare the cost with min and update min if needed.
	for(int r = i; r <= j; r++)
	{
		int cost = optCost(freq, i, r - 1) + optCost(freq, r + 1, j);
		minimum = min(minimum, cost);
	}

	// Return minimum value
	return minimum + fsum;
} // optCost()

int optimalSearchTree(vector<int> &keys, vector<int> &freq)
{
	int n = keys.size();
	return optCost(freq, 0, n - 1);
} // optimalSearchTree()

int main()
{
	vector<int> keys = {10, 12, 20};
	vector<int> freq = {34, 8, 50};

	cout << optimalSearchTree(keys, freq) << '\n';

	return 0;
} // main()