动态规划最优二叉搜索树算法

动态规划最优二叉搜索树算法的基本思想是利用最优子结构来求解问题。首先定义e[i,j]为包含关键字k[i,...,j]的最优二叉搜索树的期望搜索代价，e[1,n]为问题的最终解。算法的过程可以分为以下几个步骤：

1. 初始化：对于每个关键字k[i]，将e[i,i-1]和w[i,i-1]初始化为d[i-1]和d[i-1]的值，其中w[i,i-1]表示权重。

2. 计算子问题：对于每个子问题的长度l（从2到n），计算e[i,j]和w[i,j]的值。其中e[i,j]表示包含关键字k[i,...,j]的最优二叉搜索树的期望搜索代价，w[i,j]表示子树的权重。

3. 填表：根据最优子结构的性质，逐步填充e[i,j]和w[i,j]的值。

4. 寻找根节点：根据填表得到的e和w数组，可以找到最优二叉搜索树的根节点。

5. 构建最优二叉搜索树：根据根节点，递归地构建最优二叉搜索树。

以上就是动态规划最优二叉搜索树算法的基本步骤。通过这个算法，我们可以找到包含给定概率集合的期望搜索代价最小的二叉搜索树。