USACO Training Problem: Cow Pedigrees

This is an interesting problem that can be solved using dynamic programming.
The problem can be found here:
http://cerberus.delos.com:790/usacoprob2?a=9HnzpXyw1Xh&S=nocows

This problem is hard because it is difficult to come up with a recurrence relation.

      First note that there can not be an even number of nodes in the tree. This is easy to see since every node must have an even number of children, but there exists a single root node that makes the node count odd.
     Secondly, we can make the problem simpler by just treating a group of 3 nodes as 1 node:
For example:
        @                                    @      
        /  \             becomes         /  
     @   @                             @
     /  \
  @   @

Now the reduced tree does not have to follow the condition that each node must have 0 or 2 children.
We can create a dp state (i,j) = x, such x represents the number of trees that have at most i levels and exactly j nodes. Note that we are applying our dp state to the reduced trees.

Let's say we have a tree with at most i levels and exactly j nodes, if we consider the two branches of the root node, we have two subtrees and thus two subproblems.

Let n1 = the number of nodes in the left subtree and n2 = number of nodes in the right subtree.
We have that n1 + n2 + 1 = j.

Also, both subtrees have at most i-1 levels.

Thus, in order to find the number of ways to construct a tree with state(i,j) we must find all combinations of left subtree constructions and right subtree constructions. We can use a loop for the number of nodes in the left subtree (denoted below as m) and the number of nodes in the right subtree is clearly j-m-1.

This gives the recurrence: dp(i,j)=sum(dp(i-1,m) * dp(i-1,j-m-1)) as m goes from 0 to j-1.

It is trivial that dp(i,0) = 1 for all i. Since with 0 nodes you can construct 1 with #levels<=i for all i.

Lastly, in the problem we must find the number of tree constructions given N and K, where N is the exact number of nodes and K is the exact number of levels. However we make a reduction first, so we must set N := N/2 and K := K-1.
Now, we cannot simply retrieve dp(K,N), since in the state (i,j), i represents the upper bound of the number of levels.
Thus, the number of constructions with exactly K levels is dp(K,N)-dp(K-1,N)
Runtime: O(N^2*K)