Suppose you need a binary search tree (BST) that makes searches as efficient as possible, given the frequency of the keys. Given a list of pairs
Here is a first attempt. Denote the minimum cost of a BST comprised of nodes containing as , and the weight added by selecting some ( ) as the root with subtrees and as . You should draw some small BSTs to see why this is suitable. Now, for each each choice of with find . Again, this is close, but not identical, to the formula for triangulation and matrix multiplication, so you'll need to slightly change the notation.
Denote the minimum cost of a BST comprised of nodes containing , , as , and as the sum . Now your recursive formula is Equation 1. If you set out to find a minimal BST for values , , , the corresponding minimal cost will be , and the algorithm is the same (except for the definition of ) as the other two problems.