最优二叉搜索树的java代码，每一行都有注释

以下是最优二叉搜索树的Java代码，每一行都有注释:

public class OptimalBST {
    static int optimalSearchTree(int keys[], int freq[], int n) {
        // 计算每个关键字的权值
        int cost[][] = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            cost[i][i] = freq[i];
        }

        // 单元素的最优搜索树成本
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i <= n - L + 1; i++) {
                int j = i + L - 1;
                cost[i][j] = Integer.MAX_VALUE;

                // 枚举根节点
                for (int r = i; r <= j; r++) {
                    int c = ((r > i) ? cost[i][r - 1] : 0)
                            + ((r < j) ? cost[r + 1][j] : 0) + sum(freq, i, j);
                    if (c < cost[i][j]) {
                        cost[i][j] = c;
                    }
                }
            }
        }
        return cost[0][n - 1];
    }

    // 计算数组元素之和
    static int sum(int freq[], int i, int j) {
        int s = 0;
        for (int k = i; k <= j; k++) {
            s += freq[k];
        }
        return s;
    }

    public static void main(String[] args) {
        int keys[] = {10, 12, 20};
        int freq[] = {34, 8, 50};
        int n = keys.length;
        System.out.println("The cost of optimal BST is " + optimalSearchTree(keys, freq, n));
    }
}

这段代码使用了动态规划的思想来求解最优二叉搜索树的成本。对于每个子区间[i,j]，枚举其中的每个节点作为根节点，计算以它为根节点时的成本。动态规划的过程中，每个子问题都只需要计算一次，因此复杂度为O(n^3)。