动态规划——最优二叉搜索树

问题：

给定数据集合S与存取概率分布P，求一颗平均查找次数（平均查找长度）最小的二叉搜索树，即最优二叉搜索树。

分析：

对于一个给定的升序序列，如何构造其二叉搜索树呢？只要不断“断开”即可，换句话说，还是一个加括号问题。

m[i][j]为i到j构成的一棵子树的平均查找长度

w[i][j]为i倒j的所有节点的概率总和

假设从k处断开，那么假设其被分为左子树、右子树和根节点。如果将左右子树放在其父树中，则其所有节点的深度都会增加1，换算过来，在树中的子树平均查找长度要在子树单独存在的基础上加w。再加上根节点的平均查找长度为根节点的概率，故递推公式如下：

m[i][j] =min_i<=k<=j{m[i][k-1]+m[k+1][j]+w[i][j]}

代码和时间复杂度自然和加括号问题一样。