乐趣区

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

问题描述:
最优二叉查找树:
给定 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 时间复杂度

退出移动版