最优二叉搜索树问题是指已给出一株二叉树的中序遍历（或需要你全排列枚举），以及每个结点搜索概率，搜索到一层花费１，问如何安排这棵二叉树使搜索花费的期望值最小

这类问题的花费通常定义为结点权值乘以结点所在深度

p0*level(x0)+p1*(level(x1))+…pn-1*(level(xn-1))　这里level(xi)表示数据项xi在树中对应节点的层数(深度)

它的动态模型与合并石子相当类似

Ｆ［Ｉ，Ｊ］＝ＭＩＮ（　Ｆ［Ｉ，Ｋ－１］+Ｆ［Ｋ+１，Ｊ］+ＳＵＭ［Ｉ，Ｊ］　）

初值Ｆ［Ｉ，Ｉ］＝Ａ［Ｉ］　Ｆ［Ｉ，Ｊ］＝∞（Ｉ＜Ｊ）　Ｆ［Ｉ，Ｊ］＝０　（Ｉ＞Ｊ）

ＳＵＭ［Ｉ，Ｊ］＝Ａ［Ｉ］+Ａ［Ｉ+１］+....+Ａ［Ｊ－１］+Ａ［Ｊ］..

表示中序遍历从Ｉ到Ｊ，以Ｋ为根结点的最优值，可以理解为当你决定将Ｆ［Ｉ，Ｋ－１］，Ｆ［Ｋ+１，Ｊ］两棵子树用Ｋ作根结点连起来时，子树的点都＂多了一层＂，因而花费要加上ＳＵＭ［Ｉ，Ｊ］

我们考虑这个问题的一个实例。我们有5个数据项，按字典序排列(A,B,C,D,E)其各自的搜索概率为(0.25,0.05,0.2,0.4,0.1)。这个例子的最优值是f(１,５)=1.9)，其对应的最优二叉搜索树如图所示。