动态规划解决最优二叉搜索树的递推公式

最优二叉搜索树（Optimal Binary Search Tree，简称OBST）问题是指给定一个值序列，其中每个值作为二叉搜索树中的一个键，要求构造一棵具有最小期望搜索成本的二叉搜索树。动态规划是解决这个问题的一种有效方法。动态规划的递推公式如下：

设cost[i][j]表示以值序列中的第i个值到第j个值作为二叉搜索树的根节点时的最小期望搜索成本。则有：

1. 当i > j时，cost[i][j] = 0，因为没有节点，不需要搜索成本。

2. 当i ≤ j时，cost[i][j]的值由以下两部分决定：
- 选择某个值作为根节点，计算其左右子树的最小成本之和。
- 计算以当前根节点进行搜索时的期望成本，即每个节点被搜索的概率乘以其深度。

具体的递推公式如下：

cost[i][j] = min{cost[i][j], cost[i][k-1] + cost[k+1][j] + sum(p[i...k-1] * depth(k, i, j)) + p[k] * depth(k, i, j)}

其中，k从i到j进行遍历，p[i...k-1]表示从i到k-1的节点被搜索的概率之和，p[k]表示节点k被搜索的概率，depth(k, i, j)表示节点k在以i到j为节点构成的树中的深度。

这里的关键是如何计算深度。对于一个节点k，其深度取决于其是左子树的根还是右子树的根。如果k是左子树的根，则其深度是1加上左子树的根节点的深度；如果k是右子树的根，则其深度是1加上右子树的根节点的深度。

通过这个递推公式，我们可以利用动态规划的方法，从最小的子问题开始，逐步构建出整个问题的解。