Dynamic Programming, Binary Tree: How to factor in depth to recursion? 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 &lt; 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 &lt; 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??
Turns out that I had a misunderstanding of the scope of dynamic programming.  As I understood it, I was "not allowed" to capture other things outside the recursion besides elementary operations.  

So, I just have to literally calculate the sum of values lower than the root on either side to factor in the depth: 

$$
T(i,j) = \sum_{i\leq l &lt; j}f_l + min\lbrace + T(i,k-1) + T(k+1,j)\rbrace: i&lt;k&lt;j 
$$

Where I can just calculate the sum outside of the recursion.