最优二叉搜索树 动态规划

最优二叉搜索树（Optimal Binary Search Tree, 简称OBST）是指一种满足以下条件的二叉搜索树：

1. 对于任意一个节点，其左子树中的所有节点的值都比该节点的值小，右子树中的所有节点的值都比该节点的值大。

2. 对于一个节点，其左子树和右子树分别也是一棵二叉搜索树。

3. 对于给定的一组关键字，OBST的平均搜索代价（即搜索某个关键字所需的比较次数）最小。

为了求解OBST，我们可以使用动态规划算法。具体地，我们可以先将关键字按照其大小排序，然后定义一个二维数组dp，其中dp[i][j]表示关键字i到j构成的子树的最小搜索代价。具体的状态转移方程为：

dp[i][j] = min{dp[i][k-1] + dp[k+1][j] + w(i,j)} (i <= k <= j)

其中，w(i,j)表示关键字i到j的权值之和。这个权值可以是它们在搜索树中出现的概率，也可以是它们在搜索树中出现的频率。最终的答案即为dp[1][n]，其中n为给定的关键字个数。

在计算dp数组时，我们可以使用一个辅助数组root，其中root[i][j]表示关键字i到j子树的根节点编号。具体地，我们可以枚举i到j中的每个节点k，计算dp[i][j]的值，并更新root[i][j]的值为k。最后，我们可以根据root数组构造出OBST的结构。

时间复杂度为O(n^3)，其中n为关键字的个数。