OBST.java

import java.util.*;

class OBST {
    public static void main(String[] args) {
        System.out.println("Enter n, keys, p[i], and q[i] in order:");
        Scanner sc = new Scanner(System.in);

    
        int n = sc.nextInt();// no. of ids 

        int[] keys = new int[n];//sorted keys 
        for (int i = 0; i < n; i++) {
            keys[i] = sc.nextInt();
        }

        
        double[] p = new double[n + 1];// prob of suceessful search
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextDouble();
        }

      
        double[] q = new double[n + 1];// prob of unsucessful search
        for (int i = 0; i <= n; i++) {
            q[i] = sc.nextDouble();
        }

        double minCost = optimalBST(p, q, n);
        System.out.printf("%.4f\n", minCost);

        sc.close();
    }

    public static double optimalBST(double[] p, double[] q, int n) {
        double[][] e = new double[n + 2][n + 1]; // Expected cost
        double[][] w = new double[n + 2][n + 1]; // Weight
        int[][] root = new int[n + 1][n + 1];    // Root table 

    
        for (int i = 1; i <= n + 1; i++) { // single intervals 
            e[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];
        }

        // values for chains of increasing length
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                e[i][j] = Double.MAX_VALUE;
                w[i][j] = w[i][j - 1] + p[j] + q[j];

                //  each key k as root
                for (int r = i; r <= j; r++) {
                    double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    if (t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = r;
                    }
                }
            }
        }

        //  min expected cost stored in e[1][n]
        return e[1][n];
    }
}