动态规划练习题最优二分查找树

问题描述：
最优二叉查找树：
给定 n 个互异的关键字组成的序列 K =<k1,k2,…,kn>，且关键字有序（k1<k2<…<kn），我们想从这些关键字中构造一棵二叉查找树。对每个关键字 ki，一次搜索搜索到的概率为 pi。可能有一些搜索的值不在 K 内，因此还有 n + 1 个“虚拟键”d0,d1,…,dn，他们代表不在 K 内的值。具体：d0 代表所有小于 k1 的值，dn 代表所有大于 kn 的值。而对于 i = 1,2,…,n-1, 虚拟键 di 代表所有位于 ki 和 ki+ 1 之间的值。对于每个虚拟键，一次搜索对应于 di 的概率为 qi。要使得查找一个节点的期望代价（代价可以定义为：比如从根节点到目标节点的路径上节点数目）最小，就需要建立一棵最优二叉查找树。
举例说明：
n= 5 的关键字集合以及如下的搜索概率，构造二叉搜索树。

期望搜索代价的计算公式：

下图中图 a 显示了给定上面的概率分布 pi、qi，生成的两个二叉查找树的例子。图 b 就是在这种情况下一棵最优二叉查找树。

输入：
p 序列：表示对每个关键字 ki，一次搜索搜索到的概率为 pi；
q 序列：表示对每个虚拟键 di，一次搜索搜索到的概率为 qi。

输出：
关键字和虚拟键的中序遍历结果

思路：

1 拆分子问题

2 计算

3 代码

4 时间复杂度