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

以下是使用动态规划实现的最优二分检索树的 Java 代码：

public class OptimalBST {
    public static float optimalBST(float[] p, float[] q, int n) {
        float[][] e = new float[n + 2][n + 1];
        float[][] w = new float[n + 2][n + 1];
        int[][] root = new int[n + 1][n + 1];

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

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                e[i][j] = Float.MAX_VALUE;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int r = i; r <= j; r++) {
                    float 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;
                    }
                }
            }
        }

        return e[1][n];
    }

    public static void main(String[] args) {
        float[] p = {0.15f, 0.10f, 0.05f, 0.10f, 0.20f};
        float[] q = {0.05f, 0.10f, 0.05f, 0.05f, 0.05f, 0.10f};
        int n = p.length;
        float result = optimalBST(p, q, n);
        System.out.println("The optimal BST cost is " + result);
    }
}

其中，`optimalBST` 方法接受三个参数：`p` 表示每个关键字被查找的概率，`q` 表示每个虚拟关键字被查找的概率，`n` 表示关键字的个数。返回值为最优二分检索树的期望代价。

在 `optimalBST` 方法中，我们首先初始化 `e[i][i-1]` 和 `w[i][i-1]`，然后使用动态规划计算 `e[i][j]` 和 `root[i][j]`，最后返回 `e[1][n]` 即可。

在 `main` 方法中，我们定义了一个例子，使用 `optimalBST` 方法计算最优二分检索树的期望代价，并输出结果。