OBST

public class OBSTree {

    public static void main(String[] args) {
        double[] P = {3, 3, 1, 1};
        double[] Q = {2, 3, 1, 1, 1};

        int n = P.length;

        OBSTResult result = OBST(P, Q, n);

        System.out.println("Cost Matrix C:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%.2f ", result.C[i][j]);
            }
            System.out.println();
        }

        System.out.println("\nRoot Matrix R:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%d ", result.R[i][j]);
            }
            System.out.println();
        }
    }

    public static OBSTResult OBST(double[] P, double[] Q, int n) {
        double[][] C = new double[n + 1][n + 1];
        double[][] W = 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;
            if (i < n) {
                W[i][i + 1] = Q[i] + Q[i + 1] + P[i];
                C[i][i + 1] = W[i][i + 1];
                R[i][i + 1] = 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 - 1] + Q[j];

                double minCost = Double.MAX_VALUE;
                int bestRoot = -1;

                for (int k = R[i][j - 1]; k <= R[i + 1][j]; k++) {
                    double cost = C[i][k - 1] + C[k][j];
                    if (cost < minCost) {
                        minCost = cost;
                        bestRoot = k;
                    }
                }

                C[i][j] = W[i][j] + minCost;
                R[i][j] = bestRoot;
            }
        }

        return new OBSTResult(C, W, R);
    }
}

class OBSTResult {
    double[][] C;
    double[][] W;
    int[][] R;

    OBSTResult(double[][] C, double[][] W, int[][] R) {
        this.C = C;
        this.W = W;
        this.R = R;
    }
}

/*
Test Case 1:
Input:
P = {3, 3, 1, 1}
Q = {2, 3, 1, 1, 1}

Expected Output:
Cost Matrix C:
0.00 2.00 5.00 8.00 9.00 
0.00 0.00 4.00 7.00 8.00 
0.00 0.00 0.00 4.00 5.00 
0.00 0.00 0.00 0.00 1.00 
0.00 0.00 0.00 0.00 0.00 

Root Matrix R:
0 1 1 1 1 
0 0 1 1 2 
0 0 0 3 3 
0 0 0 0 4 
0 0 0 0 0

Test Case 2:
Input:
P = {4, 2, 3, 4, 2}
Q = {3, 1, 2, 1, 2, 3}

Expected Output:
Cost Matrix C:
0.00 3.00 7.00 10.00 15.00 18.00 
0.00 0.00 2.00 5.00 9.00 12.00 
0.00 0.00 0.00 2.00 5.00 7.00 
0.00 0.00 0.00 0.00 2.00 4.00 
0.00 0.00 0.00 0.00 0.00 2.00 
0.00 0.00 0.00 0.00 0.00 0.00 

Root Matrix R:
0 1 2 3 3 4 
0 0 1 2 3 3 
0 0 0 1 2 3 
0 0 0 0 1 2 
0 0 0 0 0 1 
0 0 0 0 0 0
*/