S2.3 Cow Pedigrees

This is a typical DP problem. Since all the trees have either two children or none, we know that all trees with depth i can be built upon those ones with depth i+1. And this is crucial to solving this problem.

We define table[i][j] as the number of legal trees with depth i and j nodes. There are 3 possibilities to build a i-depth tree.

1.       The left subtree’s depth is i-1  while  the right one’s smaller than i-1;

2.       The left subtree’s depth is small than i-1  while  the right one’s i-1;

3.       Both the left and the right subtrees’ depth are i-1.

According what we have analysed. We can define another 2-dimensional array smalltrees[i][j] to restore all the sum of trees shorter than i—from 1 to i-1—to avoid unnecessary loops when calculating. Thus, we got:

(k loops from 1 to j, increment is 1, indicating the nodes of the left subtree)

Table[i][j] += table[i-1][k] * smalltrees[i-2][j-k-1];

Table[i][j] += smalltrees[i-2][k] * table[i-1][j-k-1];

Table[i][j] += table[i-1][k] * table[i-1][j-k-1]. ①

And remember to refresh smalltrees every time:

(k indicate the depth of the tree)

smalltrees[i-1][k] += table[i-1][k] + smalltrees[i-2][k]. ①

①:After getting each value, mod process is needed.