I have the following problem.
I have a set of elements $x_0,\ldots,x_n$ which must retain their order inside the binary tree: if, given $x_i, x_j, i < j$, $x_i$ must be to the left of $x_j$ if $x_j$ is the root and $x_i$ is part of $x_j$'s subtree.
I also have a set of frequencies $f_0,\ldots,f_n$. I need to build a binary tree such that the cost of accessing the elements, defined as $depth$*$f$ is minimized.
I figured this was just like chain matrix multiply, so I wrote that the dynamic table was:
T(i,j) = minimum cost tree between i and j
And I wrote the following recurrence:
$$ T(i,j) = min \lbrace T(i,k) + T(k,j)\rbrace, i \le k < j $$
However, I can't figure out if depth is being factored in here--it appears (to me) that it isn't.
How do I construct this recurrence??