import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of keys (n):");
        int n = sc.nextInt();
        double[] p = new double[n+1];
        double[] q = new double[n+1];
        
       System.out.println("Enter probabilities of successful searches for keys (p):");
        for(int i=1;i<=n;i++){
            p[i] = sc.nextDouble();
        }
        
       System.out.println("Enter probabilities of unsuccessful searches (q):");
        for(int i=0;i<=n;i++){
            q[i] = sc.nextDouble();
        }
        obst(p,q,n);
    }
    public static void obst(double[] p,double[] q,int n){
        double[][] w = new double[n+1][n+1];
        double[][] c = new double[n+1][n+1];
        int[][] r = new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            w[i][i] = q[i];
            c[i][i] = 0;
            r[i][i] = 0;
        }
        for(int m = 1;m<=n;m++){
            for(int i=0;i<=n-m;i++){
                int j = i+m;
                w[i][j] = w[i][j-1] + p[j]+q[j];
                double mincost = Double.MAX_VALUE;
                int root = -1;
                for(int k=i+1;k<=j;k++){
                    double cost = c[i][k-1]+c[k][j]+w[i][j];
                    if(cost < mincost){
                        mincost = cost;
                        root = k;
                    }
                }
                c[i][j] = mincost;
                r[i][j] = root;
            }
        }
        System.out.println("Cost = "+c[0][n]);
        System.out.println("Weight = "+w[0][n]);
    }
}






ALGORITHM:
// Algorithm OBST(p, q, n)
// Given n distinct identifiers a1 < a2 < ... < an and probabilities
// p[i], 1 ≤ i ≤ n, and q[i], 0 ≤ i ≤ n, this algorithm computes
// the cost c[i, j] of optimal binary search trees tij for identifiers
// a[i+1],...,a[j]. It also computes r[i, j], the root of tij.
// w[i, j] is the weight of tij.
 
for i := 0 to n - 1 do
{
    // Initialize.
    w[i, i] := q[i]; r[i, i] := 0; c[i, i] := 0.0;
    // Optimal trees with one node
    w[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
    r[i, i + 1] := i + 1;
    c[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
}
w[n, n] := q[n]; r[n, n] := 0; c[n, n] := 0.0;
for m := 2 to n do // Find optimal trees with m nodes.
    for i := 0 to n - m do
    {
        j := i + m;
        w[i, j] := w[i, j - 1] + p[j] + q[j];
        // Solve 5.12 using Knuth's result.
        k := Find(c, r, i, j);
        // A value of l in the range r[i, j - 1] ≤ l ≤ r[i + 1, j] that minimizes c[i, l - 1] + c[l, j];
        c[i, j] := w[i, j] + c[i, k - 1] + c[k, j];
        r[i, j] := k;
    }
write (c[0, n], w[0, n], r[0, n]);
 
// Algorithm Find(c, r, i, j)
min := ∞;
for m := r[i, j - 1] to r[i + 1, j] do
    if (c[i, m - 1] + c[m, j]) < min then
    {
        min := c[i, m - 1] + c[m, j];
        l := m;
    }
return l;