OBST

import java.util.Scanner;

public class OptimalBinarySearchTree {

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

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

        // Input keys
        int[] keys = new int[n];
        System.out.println("Enter the keys:");
        for (int i = 0; i < n; i++) {
            keys[i] = scanner.nextInt();
        }

        // Input probabilities for each key
        double[] probabilities = new double[n];
        System.out.println("Enter the probabilities for each key:");
        for (int i = 0; i < n; i++) {
            probabilities[i] = scanner.nextDouble();
        }

        // Calculate minimum cost of Optimal BST
        double minCost = optimalBST(keys, probabilities, n);

        System.out.println("Minimum cost of Optimal BST: " + minCost);

        scanner.close();
    }

    public static double optimalBST(int[] keys, double[] probabilities, int n) {
        double[][] cost = new double[n + 1][n + 1];
        double[][] sumProb = new double[n + 1][n + 1];

        // Initialize the cost for a single key
        for (int i = 0; i < n; i++) {
            cost[i][i] = probabilities[i];
            sumProb[i][i] = probabilities[i];
        }

        // Fill cost and sumProb matrices for increasing chain lengths
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                cost[i][j] = Double.MAX_VALUE;
                sumProb[i][j] = sumProb[i][j - 1] + probabilities[j];

                // Find the minimum cost with different roots
                for (int r = i; r <= j; r++) {
                    double c = (r > i ? cost[i][r - 1] : 0) +
                               (r < j ? cost[r + 1][j] : 0) +
                               sumProb[i][j];
                    if (c < cost[i][j]) {
                        cost[i][j] = c;
                    }
                }
            }
        }

        return cost[0][n - 1];
    }
}