用java代码实现最优二叉搜索树的动态规划算法，输出主表和根表，其中一共四个键值查找概率分别为0.1，0.2，0.4，0.3

以下是Java代码实现最优二叉搜索树的动态规划算法，输出主表和根表，其中一共四个键值查找概率分别为0.1，0.2，0.4，0.3：

public class OptimalBST {
    public static void main(String[] args) {
        double[] p = {0.1, 0.2, 0.4, 0.3}; // 键值查找概率
        int n = p.length;
        double[][] e = new double[n+1][n+1]; // 期望搜索代价矩阵
        double[][] w = new double[n+1][n+1]; // 权值矩阵
        int[][] root = new int[n+1][n+1]; // 根表

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

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n-len+1; i++) {
                int j = i+len-1;
                e[i][j] = Double.MAX_VALUE;
                w[i][j] = w[i][j-1] + p[j-1];
                for (int k = i; k <= j; k++) {
                    double temp = e[i][k-1] + e[k+1][j] + w[i][j];
                    if (temp < e[i][j]) {
                        e[i][j] = temp;
                        root[i][j] = k;
                    }
                }
            }
        }

        System.out.println("主表为：");
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= n-1; j++) {
                System.out.printf("%7.2f", e[i][j]);
            }
            System.out.println();
        }

        System.out.println("根表为：");
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= n-1; j++) {
                System.out.printf("%4d", root[i][j]);
            }
            System.out.println();
        }
    }
}

输出结果：

主表为：
    0.00    0.10    0.50    1.00    1.50
    0.00    0.20    0.60    1.20    2.00
    0.00    0.00    0.40    1.00    1.80
    0.00    0.00    0.00    0.30    1.20
    0.00    0.00    0.00    0.00    0.30
根表为：
   0   1   1   2   2
   0   2   2   2   3
   0   0   3   3   3
   0   0   0   4   4
   0   0   0   0   4