求解最优二分搜索树

最优二分搜索树(即Optimal Binary Search Tree,简记为BST)的求解在一些实际问题中是经常碰到的。本文首先对该问题以及已有的几种求解算法作一介绍和评述,之后给出求解OBST的更优算法,以及其正确性证明和算法评价。该算法的时间复杂度为最好的结果9(nlogn)。