We just discovered that the minimal solution to our problem is formed out of minimal solutions to the subproblems.
Here's a question I should have explored from the beginning: How big is our solution space ? In other words, how many BST's can we construct from a sequence {1,..., n} ?
Well, the BST property (left nodes smaller than root, right nodes larger) makes constructing BST's an exercise in partitioning {1,.., n}. We pick an arbitrary number as root node and the numbers left to it will go into the left subtree which itself will be a BST and the numbers right of it will go into the right subtree which is also a BST. There are n possible root nodes and the rest we express recursively.
So if P(n) is the number of BST of n nodes we get:
P(n) = Sum(k = 1, k <= n of P(k) * P(n - k)).
Here it helps to know your classics. I'm not talking about Homer and The Illiad here. For me it's
A quick look in there reveals that P(n) is a Catalan number and O(4^n/n^(3/2)).
So our solution space is exponential and searching it brute-force will take too long.
We have (*) though so we could try to solve it recursively. Here's (*) repeated again:
(*) cost(a LS RS) = sum(probablities of all nodes in tree) + cost(LS) + cost(RS)
mincost = min (with a = 1 to n of sum(probablities of all nodes in tree) + mincost(LS) + mincost(RS))
Here's the other key observation:
the recursive solution won't be much faster. The recursive calls get called over and over again. That means solutions of bigger trees share the same solution to smaller trees.
Time to re-read the chapter on dynamic programming in the classic.
That did it, here's a small java program that solves it.
The runtime is O(n^3).
Would a greedy algorithm have done it too ? I don't think so. This problem looks too similar to the Matrix Chain Multiplication problem which is a classic dynamic programming problem. For greedy algorithms to work you need to prove that substituting a minimal local solution with a greedy local solution yields the same minimal solution to the whole problem. I couldn't prove that and in fact when looking at the example solutions given in the problem statement you can see that greedy local choices (choose the biggest probability as your root and proceed recursively) don't result in the same trees.
