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

// A dynamic program (in a generalized 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 computer
int n;

// A dynamic program (in traditional sense of this adjective)
// that computes an optimal BST
    


public void compute_BST_A (int i, int j)
{
	double[] work = new double[n];
//	int k;
	if (i > j) A[i][j] = 0;
	else 
	{
		if (i == j) A[i][j] = P[i][j];
		else 
		{
			for  (int k = i; k <= j; k++) 
			{
				// precompute A[i, k-1]
				if (A[i][k-1] < 0) compute_BST_A(i, k-1);
				// precompute A[k+1, j]
				if (A[k+1][j] < 0) compute_BST_A(k+1, j);
				// candidate for min
				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
		}
	}

}