/**
 * TODO 实现最优二叉树算法
 */
public class OptimalBinaryTree {

    public static void main(String[] args) {
        // TODO p[1, 5]是 5个实节点的概率 p[0]不存在，对应每一个关键字的搜索频率
        double[] p = {0, 0.15, 0.1, 0.05, 0.1, 0.2};
        // TODO q[0, 5]是 6个伪节点的概率
        double[] q = {0.05, 0.1, 0.05, 0.05, 0.05, 0.1};
        // TODO 一共5个关键字（可以搜索得到的，即实节点）
        int n = p.length - 1;

        // TODO root[i][j]记录的是最终得出的[i,j]这个子段里的根节点
        int[][] root = optimalBinarySearchTree(p, q, n);
        // TODO root的 length 是 n+2, i 和 j 只需要循环到 n
        int temp = root.length - 1;
        // TODO 输出一下这个root矩阵，直接根据这个矩阵也可以画出来最优二叉搜索树
        //  root矩阵将对角线旋转到水平方向更直观地看到最优二叉搜索树
        for (int i = 1; i < temp; i++) {
            for (int j = 1; j < temp; j++) {
                System.out.print(root[i][j] + "-");
            }
            System.out.println();
        }
    }

    private static int[][] optimalBinarySearchTree(double[] p, double[] q, int n) {
        // TODO e[i][j]表示 i 到 j 这段的代价
        //  e[1][0]为左边只包含伪节点d0的代价...e[n+1][n]为左边只包含伪节点dn的代价
        double[][] e = new double[n + 2][n + 2];
        // TODO i 到 j 这一段的总概率，在加一层根节点时需要用到
        //  为避免每次计算e[i, j]都重新计算w(i,j)的值，直接将这些值存放在w数组中
        double[][] w = new double[n + 2][n + 2];
        // TODO root[i][j]记录的是最终得出的[i,j]这个子段里的根节点
        int[][] root = new int[n + 2][n + 2];

        // TODO 初始化
        for(int i = 1; i < n + 1; i++) {
            e[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];     // 1 <= i <= n + 1的情况
        }
        // TODO ：l是 [i, j]区间的长度，相当于一个固定l长度的小节从最左边循环到最右边。
        //  然后再把l逐渐加大，重复从左到右。
        //  这样就使得小长度的都先计算过，为大长度的片段分解为左右两个子片段计算时提供了已经计算好的值，这也是动态规划的精髓之一。
        //  这样做是为了从小到大积累动态规划的能量
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                // TODO 初始化为最大值，最后才能找出真正最小的，从而找到最优解
                e[i][j] = Double.MAX_VALUE;
                // TODO j >= i的情况
                w[i][j] = w[i][j-1] + p[j] + q[j];
                // TODO 从 i 到 j 找到最优的根节点（选择以 r 为根节点）
                for(int r = i; r <= j; r++) {
                    // TODO 加了一层，相当于下面的左子树右子树都加了一布，其实就是最终比没加一层根节点比多了一个w[i][j]
                    double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    // TODO 不断的使e[i][j]保持最小，同时记录下使代价最小的位置为最终的最优的根节点
                    if(t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = r;
                    }
                }
            }

        }
        System.out.println("当前最小代价：" + e[1][n]);
        return root;
    }
}