Auto comment: topic has been updated by ankeshgupta007 (previous revision, new revision, compare).

First, you need to sort the values in non-decreasing order.

In this question, first of all, to think of a solution that will require O(n^3) space and O(n^4) time is actually pretty easy.

The States would be i,j,k where dp[i][j][k] would represent the min value of arranging the numbers from index i to j in a BST such that the root node is at a depth k. Now to calculate the value of dp[i][j][k] we will iterate from index i to j and consider one by one each index as the root. We can easily think of the recurrence for this. So I am assuming you already know that part.

Now in the above approach, we are keeping the depth also as a state. To reduce the complexity by a factor of n we can avoid keeping depth as a state. I will roughly explain my approach the main idea is if you have the value wi * (hi ^ 2) for any index i, when you will increase the depth by 1 the new value would be something like this wi * ((hi + 1)^2) which can be derived from the previous value directly. All you need is some extra values while calculating the new values,

wi * ((hi + 1)^2) = wi*(hi^2 + 1 + 2*hi)

which is wi*(hi^2) + wi + 2*wi*hi.

So the extra values which we need to store is summation of wi and summation of wi*hi. And you can get the new value which is wi * ((hi + 1)^2). And its also easy to get the new value of wi*(hi + 1). Because that would be wi*hi + wi and both the values are already there.

PS: I know I have not provided a good explanation but I think if you have the idea of the straight forward dp of this question you will get the idea of optimization from my explanation.

Can you please tell me the name of the book?

Sort all the values in increasing order of a_i's. We can then do something like dp[i][j][level] where the dp value denotes the cost for the binary search tree on values from a_i to a_j, with the root at depth = level. The recurrence is dp[i][j][level] = min(dp[i][k-1][level+1] + dp[k+1][j][level]+w_k*level^2) for k from i to j. This is O(N^2) space (we can keep only 2 columns for the level), but O(N^4) time.

I will continue from the solutions proposed by others. Let dp_h, l, r be the best value we can get if we arrange the numbers indexed from l to r such that the root of the tree is at depth h. The recurrence is, of course:

dp_h, l, r = min_{l ≤ i ≤ r}(dp_{h + 1, l, i - 1} + w_ih² + dp_{h + 1, i + 1, r})

We can build the solution in layers. The last layer is h = n, and here we only need to compute dp_h, l, l, since we can never build a tree with more than one node at depth n. The same logic applies for other values of h. For example, when h = n - 1, we only need to compute DP values where r - l ≤ 1. In general, we only need to compute DP values where r - l ≤ n - h.

I think that Knuth's optimization trick will work here. This would mean that we can compute each DP state in amortized constant time, so O(n³) total. Since we only need to track the last two DP layers this is O(n²) memory.

Can anyone prove the required property or give a counterexample?

EDIT:

Here's my stress test (100 random samples), and the O(n³) solution passed.