Given keys with access frequencies , build a BST to reduce expected search cost. If key is at depth , cost is . Deeper keys cost more.
This is the problem Knuth designed his improvement for. The interval DP structure comes from the recursive BST definition. Read the problem statement carefully, noting the constraints. Try to identify the recursive structure before looking at the solution.