最优二叉搜索树 动态规划

最优二叉搜索树是一种特殊的二叉搜索树，它的查找效率比普通的二叉搜索树要高，因为它的平均查找次数更少。

在最优二叉搜索树中，根节点的键值是整棵树中键值的中位数，左子树中的键值均小于根节点的键值，右子树中的键值均大于根节点的键值。因此，最优二叉搜索树的构建需要考虑键值出现的概率，以及每个节点作为根节点时的查找次数。

动态规划是一种常见的求解最优二叉搜索树的方法。具体来说，我们可以定义一个二维数组dp[i][j]表示从i到j的最优二叉搜索树的期望查找次数。对于dp[i][j]，我们可以枚举它的根节点k，将其分成左子树(i, k-1)和右子树(k+1, j)，然后计算左右子树的期望查找次数，再加上根节点的查找次数p[k]，就可以得到dp[i][j]的值。

具体来说，dp[i][j]的计算公式如下：

dp[i][j] = min{dp[i][k-1] + dp[k+1][j] + sum(p[i...j])}，其中i<=k<=j

其中，sum(p[i...j])表示键值在区间[i,j]内的出现概率之和。通过这个公式，我们可以递归地计算所有的dp[i][j]，最终得到最优二叉搜索树的期望查找次数dp[1][n]。

最优二叉搜索树的动态规划算法的时间复杂度为O(n^3)，其中n为节点数。