高度为k的二叉树个数(递推分析)
题目：http://www.nocow.cn/index.php/Translate:USACO/nocows
题意：给定n个节点，求形成高度为k且出度只能为0或2的二叉树的个数。
分析：我们用dp[n][k]来表示n个节点深度为k的上述二叉树的个数。很明显，如果n为偶数，那么dp[n][k]=0，所以我们只
考虑n为奇数的情况。
#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int MOD = 9901;const int N = 204;const int M = 105;int dp[N][M];int f[N][M];void Init(){ memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); dp[1][1] = 1; for(int k=1;k<M;k++) f[1][k] = 1; for(int k=2;k<M;k++) { for(int i=3;i<N;i+=2) { int sum = 0; for(int j=0;j<=i-2;j++) sum = (sum + dp[j][k-1]%MOD*(f[i-1-j][k-2]%MOD*2 + dp[i-1-j][k-1]%MOD))%MOD; dp[i][k] = sum; f[i][k] = (f[i][k-1]%MOD + dp[i][k]%MOD)%MOD; } }}int main(){ int n,k; Init(); while(cin>>n>>k) cout<<dp[n][k]<<endl; return 0;}