OBST

import java.util.Scanner;

public class OBST {
    private double[][] w;
    private double[][] c;
    private int[][] r;

    public OBST(int n, double[] p, double[] q) {
        w = new double[n + 1][n + 1];
        c = new double[n + 1][n + 1];
        r = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            w[i][i] = q[i];
            r[i][i] = 0;
            c[i][i] = 0.0;

            if (i < n) {
                w[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
                r[i][i + 1] = i + 1;
                c[i][i + 1] = w[i][i + 1];
            }
        }

        for (int m = 2; 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];
                int k = findOptimalRoot(i, j);
                c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
                r[i][j] = k;
            }
        }
    }

    private int findOptimalRoot(int i, int j) {
        double minCost = Double.POSITIVE_INFINITY;
        int optimalRoot = i;

        for (int m = r[i][j - 1]; m <= r[i + 1][j]; m++) {
            double cost = c[i][m - 1] + c[m][j];
            if (cost < minCost) {
                minCost = cost;
                optimalRoot = m;
            }
        }

        return optimalRoot;
    }

    public void printResult() {
        System.out.println("Cost of Optimal BST: " + c[0][w.length - 1]);
        System.out.println("Root of Optimal BST: " + r[0][w.length - 1]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of keys: ");
        int n = scanner.nextInt();

        double[] p = new double[n + 1];
        double[] q = new double[n + 1];

        System.out.println("Enter the probabilities of keys (p[1] to p[" + n + "]):");
        for (int i = 1; i <= n; i++) {
            System.out.print("p[" + i + "]: ");
            p[i] = scanner.nextDouble();
        }

        System.out.println("Enter the probabilities of dummy keys (q[0] to q[" + n + "]):");
        for (int i = 0; i <= n; i++) {
            System.out.print("q[" + i + "]: ");
            q[i] = scanner.nextDouble();
        }

        OBST obst = new OBST(n, p, q);
        obst.printResult();

        scanner.close();
    }
}





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;