这是一个经典的动态规划问题（但厉害的是其中带有一个很神奇的定理），问题是这样的：已知二叉搜索树中每个节点的访问概率，问这棵树整体的搜索时间最短是多少（此时称为最优二叉搜索树）。
众所周知，在二叉搜树中，一次搜索的时间等于待访问节点的深度。所以整体的搜索时间为：
所以如果要整体搜索时间最短，则访问概率高的节点应该比较靠近根节点。乍一听，好像是哈夫曼编码。但是不同的是，这是二叉搜索树，所有节点的左右顺序（这里指中序遍历的顺序）不能变化。所以无法像哈夫曼编码那样一味地把概率高的节点往上移（那是一个贪心算法）。
那该怎么办呢？其实我们只要想到这样一个递推关系：一棵树如果是最优二叉搜索树，那么要么它是空树，要么它的左、右子树也是最优二叉搜索树。这样就得到了动态规划的解法：
| For size = 1到n For 所有包含size个元素的子树 For 该子树的所有节点i 找出其中一个i，使当它为根节点时，左、右子树的最短搜索时间之和最小。那么该子树的访问时间就是： 左、右子树的最短搜索时间之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）。 |
| 设一个子树的节点为i ～ j（当然，这里说的i ～ j都是从小到大排好序的），则当它是最优二叉搜索树时的根节点root(i, j)满足： root(i, j - 1) <= root(i, j) <= root(i + 1, j)。(至于这个定理是如何得来的，很深奥唉，我也不了解。但是一定要会用。) |
这样一来，上面那个算法的第3个For就可以不用循环子树中的所有节点了，只要循环另两个子树的根节点之间的范围就可以了。而这个范围根据实践表明是很小的。所以整体的时间复杂度就相当于两层For循环而已。
可以利用这个算法来解决UVA#10304，原题在http://online-judge.uva.es/p/v103/10304.html
