One of the best Tech Question and Answer I have seen..
I really tried to find equivalent algorithm for the same. I ended up looking at Kanpsack etc..
After some time I felt my thinking is going to be NP-Complete, So, I checked the mail thread itself..
I liked following answer .. Here we go ..
The cutting sticks problem—given a stick of length L and a set of
points where it has to be cut. If the cost of making a cut is equal to
the length of the stick, what is the best algorithm to find the
optimal sequence of cuts(giving minimum cost)
As I understand it, this is equivalent to finding an optimum binary search tree, where the stick length has been normalized to 1. The cut points represent keys, and the segment lengths between cuts represent the probability that a search falls between (or at the ends, below or above) the search keys. The top node of the BST represents the cut on the initial stick, while the child subtrees represent the cuts on the subdivided portions of the stick. The cost of the BST is the sum over the nodes of the probability of each key comparison. This node cost corresponds directly to length of the stick when the cut corresponding to the key is performed.
Willem gave an example which had a stick of length 1, with cuts at 0.45, 0.5, and 0.55. As a BST tree his solution would look like this (use a fixed width font):
+-(0.45,1)–+
v v
[0.45] +-(0.55,0.55) -+
v v
+-(0.5,0.1)-+ [0.45]
v v
[0.05] [0.05]
Each node is represented by (K,P) where K is the key (or cut point position in the original stick) and P is the search probability (or length of the stick at the time the corresponding cut was made). Each leaf is represented by [Q] where Q is the probability the search finds the leaf (or alternately Q is the length of corresponding cut segment).
Knuth’s The Art of Computer Programming (Vol. 3) covers algorithms for optimum BSTs in section 6.2.2. The Hu-Tucker algorithm can be used since the probability that a search will match a key exactly is effectively 0. A suitable implementation will create an optimum BST in time O(N log N). It is more complex than dynamic programming algorithm James Dow Allen gave, so I am not going to try to explain it here. It has some similarities, however, to the algorithm for finding an optimal Huffman coding. There may even be faster algorithms, since this seems to be a well-studied area.
For those without access to Knuth’s books, Google found the thesis at http://www.cs.rit.edu/~std3246/thesis/thesis.html. This has a more detailed description of the Hu-Tucker algorithm.
Jack Rouse
Thanks to Jack Rouce ..