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

// A recursive program
// that computes an optimal BST
    
    
double[][] P; // given and computed probabilities 
double[][] root; // to compute root
int n;






public double compute_BST_A (int i, int j)
{
	double[] work = new double[n];
	double toReturn;
	if (i > j) toReturn = 0;
	else 
	{
		if (i == j) toReturn = P[i][j];
		else 
		{
			for  (int k = i; k <= j; k++) 
				work[k] = compute_BST_A(i, k-1) + compute_BST_A(k+1, j);
                        // both (k-1)-i and j-(k+1) are less than j-i
                        // so the recursive calls will eventually halt
			toReturn = work[i]; // first candidate for min
			root[i][j] = i;    // corresponding candidate root
			for (int k = i + 1; k <= j; k++) 
				if (toReturn > work[k]) 
				{
					toReturn = work[k]; // next candidate for min
					root[i][j] = k;
                                }   // corresponding root
			toReturn += P[i][j]; // final result
		}
	}
        return toReturn;
}