动态规划习题之最优二叉搜索树
给定一个n元素的中序序列，它可以有卡特兰数个不同形状的二叉排序树。（卡特兰数的定义及证明参见组合数学）：
，如果我们知道每个键的查找概率，怎么来构造一个平均查找代价最小（查找成功）的最优二叉查找树呢？
用动态规划来求解，首先要找到它的最优子结构性质，然后根据这个最优子结构来描述和刻画问题，得到状态转移的方程：
看看一颗最优二叉查找树是怎么得到的？逆向思维，如果现在有一棵最优二叉查找树，root是ak，很容易得出：ak的左右子树也是最优二叉查找树（如果它的子树不是最优的，那就说明这个子树还可以继续调整，那么ak那颗树就也不是最优的了）。
用C[i , j]表示从 i 到 j 的最优二叉查找树的代价，那么问题就被划分为了n^2个子问题了（顶点号从0计数），假设有n个顶点，那么我们的目标是要求C[0 , n-1]。（编号从0还是1开始无所谓，在编程的时候注意下标范围就行了）。
现在根据它的最优子结构来找状态转移方程：从 i 到 j的一个最优二叉查找树是怎么得到的？（即一个C[i , j]是怎么来的），它是从 i 到 j 之间的顶点中选出一个顶点来做root，假设选出的这个做root的顶点是 k （i = k = j ）,那么显然有：
这个式子其实可以直接想到，不用那么复杂的推导，它就是要找一个能使得C[i , j]代价最小的 k （这个k的范围在 i 到 j之间），而后面为什么要加一个从i到j的概率呢？因为挑出了k后，它作root，每个点的查找长度都增加了1。当然，也有更严格
3）有了状态转移方程，就可以画个矩阵看看初始条件，以及每个C[i , j]依赖那些值（填表顺序）。
注意状态转移方程里当 k = i 或者 k = j 时，C[i , i - 1] 或者 C[j+1 , j]是没有定义的，在编程中只需要特殊处理下就行：对于这种没有定义的取0，其他的取矩阵中的值。
最后一点，至于具体的实现，tmd书上总喜欢画一个不是从0开始的表，有时候甚至还横坐标从0开始，纵坐标从1开始，虽说
是为了填矩阵的方便，但看起来很狗。我一般n规模的问题，就开n * n的矩阵，下表从0到n-1，对超出边界的做一些特殊处
理就行了，就像的C[i , i-1]。看看书上的表（理解意思，具体实现我开的矩阵不一样，下标控制不一样）：
它这样来画表其实就是为了解决C[i , i-1]不在定义范围内，为了能直接从矩阵中取值才这么做的。
就构造出了最优二叉查找树的最优代价的动态规划过程，利用上述状态转移方程可以填出所有的C[i , j]。
还有一个问题，怎么去不仅仅得到C[i , j]这个代价，更要知道对应于这个代价的二叉树的形状？
仍然是构造一个矩阵 A[0...n-1，0...n-1] 来记录动态规划的过程，每次选出一个 k 作root时，就把 k 记录下来，即用A[i , j] = k 表示从 i 到 j 的最优二叉查找树的root是 k。（它还蕴含从 i 到 k - 1是左子树，k+1到 j 是右子树，注意我们给定的从0到n-1顶点是一个中序序列！）
初始值 A[i , i] = i，表示只有自己的最优二叉查找树的root就是它自己。最后将得到一个矩阵A。它表达了二叉查找树的形状，当然，还得根据A的含义，从A中获取从 i 到 j的最优二叉查找树的形状。
可以有下列算法，从A中输出从 i 到 j 的最优二叉查找树的形状（输出它的前序序列，因为中序序列是已知的）：
//接受一个中序序列的点的查找概率数组，返回最优的二叉查找树的代价（注意P中的概率按顺序对应于点的中序序列）