用java完成最优二分检索树的代码

下面是用Java实现最优二分检索树的代码：

public class OptimalBST {

    public static void main(String[] args) {
        int[] keys = {10, 12, 16, 21};
        double[] p = {0.04, 0.06, 0.08, 0.02, 0.10};
        int n = p.length - 1;

        double[][] w = new double[n + 2][n + 1];
        double[][] c = new double[n + 2][n + 1];
        int[][] r = new int[n + 2][n + 1];

        for (int i = 1; i <= n + 1; i++) {
            w[i][i - 1] = p[i - 1];
            c[i][i - 1] = 0;
            r[i][i - 1] = 0;
        }

        for (int d = 0; d <= n; d++) {
            for (int i = 1; i <= n - d + 1; i++) {
                int j = i + d - 1;
                w[i][j] = w[i][j - 1] + p[j] + qSum(p, i, j - 1);
                c[i][j] = Double.MAX_VALUE;

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

        System.out.println("The minimum cost of a binary search tree is: " + c[1][n]);
        System.out.println("The root of the binary search tree is: " + r[1][n]);
    }

    private static double qSum(double[] p, int i, int j) {
        double sum = 0;
        for (int k = i; k <= j; k++) {
            sum += p[k];
        }
        return sum;
    }
}

这个代码实现了动态规划算法来计算最优二分检索树。其中，数组`w`用于存储权值，数组`c`用于存储代价，数组`r`用于存储根节点。函数`qSum`用于计算权值的累加和。最后输出的是最小代价和根节点的位置。