最优二叉搜索树
最优二叉搜索树（Optimal Binary Search Tree, OBST）是动态规划的经典问题。
二叉搜索树定义
二叉搜索树是一种二叉树：左子树所有节点值均小于该结点，右子树所有结点均大于该节点，左右子树都是二叉搜索树。中序遍历二叉搜索树即可得到有序序列。
问题描述
在搜索情境下，已知搜索关键字 k 的概率和搜索失败情况 d 的概率，求一种树的构建方式，使得搜索树的期望代价最小。
优化解结构
一个优化解包含的子树一定也是该子树的优化解。
一个树的优化解就是以其中一个结点为根，左右子树都是优化解，且总代价比以其他结点为根的方案都小。
代价传递方程
注意加上 W（增加树的高度使每个结点的代价上升一个概率）。
自下向上计算
最下层代表只有 d 元素，从 i=j 开始才加入 k 元素。
与哈夫曼树的区别
- 最优二叉搜索树：顺序固定，在顺序不变的情况下找到最优构建方法
- 哈夫曼树：顺序没有规定，通过贪心思想在每一步选择当前最小的两个结点合并
链接到
- 上一个知识点：2.3 最长公共子序列
- 下一个知识点：2.5 0-1背包问题