最优二叉搜索树问题

最优二叉搜索树是指一种特殊的二叉树，它有以下两个特点：

1. 每个节点都存储了一个键值，并且节点的键值按照一定规则排列。

2. 左子树以及右子树都是二叉搜索树。

最优二叉搜索树问题是指如何根据一组键值以及它们被搜索的概率，构建一棵二叉搜索树，使得期望搜索的次数最少。这是一个经典的动态规划问题，被广泛应用于信息检索、编译器、哈希表等领域。

动态规划算法

构建最优二叉搜索树的动态规划算法可以分为以下两个步骤：

1. 构建一棵前缀子树。也就是说，在确定最优二叉搜索树的过程中，可以先考虑某一棵不完整的子树，它的所有节点都是原问题中节点的子集。如果这个子树已经构建好，那么后面的操作就是在这个子树的基础上添加新节点或者将已有的节点从子树中删除。

2. 计算子问题的最优解。接下来，需要计算所有可能的前缀子树的最优解，并比较它们的成本。如果已有的子树最优，那么就不需要做任何操作。如果不是，则需要根据最优的子树进行相应的旋转、添加或删除节点。

最优子树的搜索

为了计算最优子树的成本，需要先确定每个节点的搜索概率。搜索概率可以通过多种方式表示，一个常用的表示方法是使用一个数组P，其中P(i)表示第i个节点的搜索概率。数组Q同样表示概率，但指代的是虚拟节点。在这个问题中，虚拟节点是一种不存在于树中的节点，用于补充树的不完整性。

从搜索概率的角度观察，最优二叉搜索树问题是一种期望值最小化问题。期望值越小，意味着搜索一次所需要的平均代价越小。

实现过程中，需要计算一个边界框，它包含了一组连续的节点。边界框对应一段区间，其中的节点是该区间内键值的一部分。每个边界框的长度都不超过n，而所有的边界框组成了所有可能的前缀子树。

全局最优解

最终的目标是要求出全局最优解，即在所有前缀子树中最小化期望搜索代价。只有当整个树都已经构建时，全局解才能得到确定。为了降低时间复杂度，可以采用动态规划的思想，先计算所有长度小于k的子树的最优解，再计算长度为k的子树，直到计算出最终的全局解。

算法复杂度

最优二叉搜索树问题的算法复杂度可以用时间复杂度和空间复杂度来表示。

时间复杂度：O(n^3)

空间复杂度：O(n^2)

空间复杂度是指算法所需要的内存空间大小。由于算法需要创建子树，所以，最优二叉搜索树问题的空间复杂度是符合预期的。