最优二叉搜索树java

最优二叉搜索树（Optimal Binary Search Tree）是一种动态规划问题，它的目标是在给定一组值及其对应的查找概率的情况下，构造出一个二叉搜索树，使得查找这些值的平均代价最小。下面是Java实现最优二叉搜索树的代码：

public static float optimalSearchTree(float[] p, float[] q, int n) {
    // e[i][j]表示子树i~j的最小代价
    float[][] e = new float[n + 2][n + 1];
    // w[i][j]表示子树i~j的权重和
    float[][] w = new float[n + 2][n + 1];
    // root[i][j]表示子树i~j的根节点
    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];
    }
    
    // 计算子树i~j的最小代价及其根节点
    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];
}

其中，`p`数组表示每个值的查找概率，`q`数组表示每个虚拟节点的概率，`n`表示值的个数。函数返回值为构造出的最优二叉搜索树的平均代价。