//Copyright Dr. Marek A. Suchenek 2011 - 2025

// A dynamic program (in traditional sense of this adjective)
// that computes an optimal BST
    
double[][] P; // given and computed probabilities 
double[][] A; // to compute; initialize to -1
double[][] root; // to compute root
int n;

.
.
.


public void compute_BST_A (int i, int j)
{
	double[] work = new double[n];
//	int k;
	if (i > j) A[i][j] = 0; // this will never happen
	else 
	{
		if (i == j) A[i][j] = P[i][j];
		else 
		{
			for  (int k = i; k <= j; k++) 
				work[k] = A[i][k-1] + A[k+1][j];
			A[i][j] = work[i]; // first candidate for min
			root[i][j] = i;    // corresponding candidate root
			for (int k = i + 1; k <= j; k++) 
				if (A[i][j] > work[k]) 
				{
					A[i][j] = work[k]; // next candidate for min
					root[i][j] = k;
                                }   // corresponding root
			A[i][j] += P[i][j]; // final result
		}
	}

}

.
.
.

for (int dif = 0; dif < n - 1; dif++)
 	// compute A[i, j] for all i, j such that j - i == dif
	// j - dif == i, so i <= n - dif
	// j = i + dif
	for (int i = 1; i <= n - dif; i++)
		compute_BST_A (i, i + dif);
//now A[i, j] has been computed for all j - i < n - 1
compute_BST_A (1, n);
// root[i][j] has been computed for all i, j, such that 1 <= i <= j <= n.