题意：给你一棵数的节点个数以及它的高度，已知这棵树的每个节点，要么有两个孩子，要么没有孩子，问你有多少种不同的构造方法（mod 9901）
解题思路：这个题首先要考虑到的就是组合数的取摸，（http://hi.baidu.com/aekdycoin/item/e051d6616ce60294c5d249d7），然后我最开始想到的方法是dfs。。发现超时，原因是一层中的节点，我们只需要考虑其个数，不需要考虑其位置，最后想到了3维DP，三个参数分别为层数，这层节点的个数，以及还剩下节点的个数，
解题代码：
1 // File Name: nocows.cpp 2 // Author: darkdream 3 // Created Time: 2013年12月12日 星期四 09时07分51秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 /* 25 ID: dream.y1 26 PROG: nocows 27 LANG: C++ 28 */ 29 using namespace std; 30 #define M 9901 31 int dp[105][150][205]; 32 int n , m ; 33 int ans = 0 ; 34 int f[150][150]; 35 int main(){ 36 freopen("nocows.in","r",stdin); 37 freopen("nocows.out","w",stdout); 38 memset(f,0,sizeof(f)); 39 memset(dp,0,sizeof(dp)); 40 clock_t be,en; 41 for(int i = 1;i <= 100;i ++) 42 f[i][i] = f[i][0] = 1; 43 for(int i= 2;i <= 100;i ++) 44 for(int j = 1;j < i; j ++) 45 f[i][j] = (f[i-1][j] + f[i-1][j-1])%M; 46 scanf("%d %d",&n,&m); 47 dp[1][1][n-1] = 1; 48 for(int i = 2;i <= m;i ++) 49 { 50 for(int j= 1;j <= 150 ;j ++) 51 for(int t = 2;t <= n-j; t += 2) 52 { 53 if(dp[i-1][j][t]) 54 { 55 for(int s = 2;s <= t && s/2 <= j;s += 2) 56 { 57 dp[i][s][t-s] = (dp[i][s][t-s] +dp[i-1][j][t]* f[j][s/2]) % M; 58 } 59 } 60 } 61 62 } 63 for(int i = 1;i <= 100;i ++) 64 ans += dp[m][i][0] ; 65 printf("%d ",ans % M); 66 return 0; 67 }
另一种方法：一棵树的状态是取决于它左右子节点！