动态规划最优二叉搜索树

动态规划最优二叉搜索树，又叫做最优二叉查找树，是指在一棵二叉查找树中，查找每个节点的概率给定，如何构造一棵高度最小、查找代价最小的二叉查找树。

动态规划最优二叉搜索树的解法是基于最优子结构和无后效性的原理，可以看做是一种自底向上的求解方法。具体来说，它通过计算不同子树的最优解，并将其组合成更大的子树的最优解，最终得到整棵树的最优解。

算法的基本思想是：用一个二维数组dp[i][j]表示从节点i到节点j构成的最优二叉搜索树的代价，其中i<=j，对于i>j的情况，dp[i][j]的值为0。通过填表格的方式，我们可以依次求出dp[1][n]，即整棵二叉搜索树的最优代价。

具体来说，我们可以按照以下步骤进行动态规划：

1. 初始化dp数组，将所有对角线上的元素设为对应节点的查找概率；
2. 从小到大枚举区间长度len，对于每个长度为len的区间[i, i+len-1]，枚举其根节点j，计算dp[i][i+len-1]的值；
3. 对于每个区间[i, i+len-1]，计算其左子树和右子树的最小代价，然后将它们相加得到dp[i][i+len-1]的值；
4. 最终dp[1][n]即为整棵树的最小代价。

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