动态规划2最优二叉搜索树

最优二叉搜索树问题是指在一棵二叉搜索树中查找某个节点的期望代价最小。其中，期望代价是指查找某个节点所需的平均搜索次数。这个问题可以使用动态规划来解决。具体来说，我们可以定义一个二维数组dp[i][j]表示从i到j的节点构成的子树中的最小期望代价。然后，我们可以通过枚举根节点来递归地计算dp[i][j]。最后，整棵树的最小期望代价就是dp[n]，其中n是节点总数。

在计算dp[i][j]时，我们可以枚举k作为根节点，然后将子树分为左子树和右子树。假设左子树的节点范围是[i,k-1]，右子树的节点范围是[k+1,j]，那么dp[i][j]可以通过以下公式计算得到：

dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + sum[i][j]

其中，sum[i][j]表示从i到j的节点的概率之和。这个公式的意义是，我们先假设k是根节点，然后计算左子树和右子树的最小期望代价，再加上根节点的代价和。最后，我们枚举所有可能的根节点，选择最小的那个作为dp[i][j]的值。

需要注意的是，我们需要先计算出所有长度为1的子树的最小期望代价，然后再逐步计算出长度为2、3、4……n的子树的最小期望代价。这样才能保证每一层的计算都是基于上一层的最优解的。