2.3.2 COW PEDIGREES 奶牛家譜

解題思路：    

1.簡(jiǎn)單動(dòng)態(tài)規(guī)劃?；舅枷胧怯眯〉亩鏄?shù)去組成大的二叉樹(shù)，最后輸出dp[k][n]-dp[k-1][n]恰好就是要求的n個(gè)點(diǎn)組成深度最多為k的方法數(shù)

2.設(shè)dp[i][j]表示j個(gè)點(diǎn)組成深度最多為i的二叉樹(shù)的方法數(shù)，則動(dòng)態(tài)規(guī)劃公式為：

   dp[i][j]=∑(dp[i-1][l]*dp[i-1][j-1-l])(1<=l<=j-2)

   dp[i][1]=1

3.注意：點(diǎn)的個(gè)數(shù)總為奇數(shù)。

核心代碼：

for(i=1;i<=k;i++)
    dp[i][1]=1;
for(i=1;i<=k;i++)
    for(j=3;j<=n;j+=2)
        for(l=1;l<=j-2;l+=2)
            dp[i][j]=(dp[i][j]+dp[i-1][l]*dp[i-1][j-1-l])%9901;