最优二叉查找树的填表过程

最优二叉查找树（Optimal Binary Search Tree）的填表过程可以通过动态规划来实现。假设有 $n$ 个节点，我们定义 $e_{i,j}$ 表示节点 $i$ 到节点 $j$ 中最优二叉查找树中所有节点被访问的期望代价，$w_{i,j}$ 表示节点 $i$ 到节点 $j$ 中所有节点的权值和，其中 $i\leq j$。

则最优二叉查找树的填表过程如下：

1. 初始化所有单个节点的期望代价和权值 $e_{i,i}=w_{i,i}$，$w_{i,i}=p_i$（$p_i$ 表示节点 $i$ 的概率）。

2. 对于每个长度 $l=2,3,...,n$ 的区间 $[i,j]$，计算 $e_{i,j}$ 和 $w_{i,j}$：

$e_{i,j}=\min\limits_{i\leq k\leq j}\{e_{i,k-1}+e_{k+1,j}+w_{i,j}\}$

其中 $k$ 表示最优二叉查找树的根节点。

$w_{i,j}=w_{i,j-1}+p_j$

3. 最终的最优二叉查找树的期望代价为 $e_{1,n}$。

注：以上填表过程中的下标从 $1$ 开始计算。