这题算是整死了，大大的Debug了一番。
大意是一个二叉树，点的度数只能为0或2，给出节点数和数的高度，问有多少种树，即树的计数问题。
用的是DP，f(i,j)表示i个节点构成j高度的树的个数，其中在转移的时候还需要small(i,j),表示i个节点的高度小于等于j的树的个数。
然后f(i,j)=f(left,j-1)*small(right,j-2)+small(left,j-2)*f(right,j-1)+f(left,j-1)*f(right,j-1)
1 #include < iostream > 2 #include < string > 3 #include < string .h > 4 #include < vector > 5 #include < math.h > 6 #include < time.h > 7 using namespace std; 8 9 const int M = 9901 ; 10 11 int small[ 205 ][ 105 ]; 12 int s[ 205 ][ 105 ]; 13 int no = 0 ; 14 15 // contruct a depth(<=k) tree with n nodes 16 int getSmall( int n, int k) 17 { 18 // if(n % 2 == 0) return 0; 19 int res = 0 ; 20 if (n == 1 && k >= 1 ) return 1 ; 21 if (n == 0 || k <= 0 ) return 0 ; 22 if (small[n][k] != - 1 ) return small[n][k]; 23 for ( int i = 0 ; i <= n - 1 ; i ++ ) 24 { 25 int left = i; 26 int right = n - 1 - i; 27 res += getSmall(left, k - 1 ) * getSmall(right, k - 1 ); 28 res %= M; 29 } 30 small[n][k] = res; 31 return res; 32 } 33 34 int dfs( int n, int k) 35 { 36 // if(n % 2 == 0) return 0; 37 int res = 0 ; 38 if (n == 1 && k == 1 ) return 1 ; 39 if (n == 0 || k == 0 ) return 0 ; 40 if (s[n][k] != - 1 ) return s[n][k]; 41 for ( int i = 0 ; i <= n - 1 ; i ++ ) 42 { 43 int left = i; 44 int right = n - 1 - i; 45 int t = res; 46 res += dfs(left, k - 1 ) * getSmall(right, k - 2 ); 47 res %= M; 48 res += dfs(right, k - 1 ) * getSmall(left, k - 2 ); 49 res %= M; 50 res += dfs(left, k - 1 ) * dfs(right, k - 1 ); 51 res %= M; 52 } 53 s[n][k] = res; 54 return res; 55 } 56 57 int main() 58 { 59 // freopen("nocows.in", "r", stdin); 60 // freopen("nocows.out", "w", stdout); 61 62 int n, k; 63 scanf( " %d%d " , & n, & k); 64 memset(small, - 1 , sizeof (small)); 65 memset(s, - 1 , sizeof (s)); 66 printf( " %d\n " , dfs(n, k)); 67 }
到dp的转移方法和状态表示清楚后，其实就简单了，可是这里却出现了很悲剧的结果，花了很长的时间终于找出了原因。
getSmall函数中，原来是这样：
1 if (n == 1 && k >= 1 ) return 1 ; 2 if (n == 0 || k == 0 ) return 0 ;这样没处理K<0的情况，这在dfs中是不会出现的，但这里由于从dfs中传递过来的，
res += dfs(left, k - 1) * getSmall(right, k - 2);
这里的k可能为1，所以就可能传进一个负数K了。
在test 7挂掉了，数据是这样的:N=172,K=44，按理来说根据二叉树的性质，这里能推倒出N应为一个奇数，偶数时应该为ANS应该为0.
然后结果却大于0，Debug中发现small[8][42]为1，可没有地方能让它赋值为1啊。。。
这就是因为传入了负数K，递归的次数会应为N而有限，所以递归没爆栈，可是当n=8，k=-63时，发生了件出乎意料又情理之中的事情。
small[8][-63]=c时，赋的就是small[8][42]的值。
通过这次Debug，晓得越界真是件可怕的事情。
贴AC后的爽图，娘的。
感谢：
http://hi.baidu.com/leokan/blog/item/a8fca034599fd0b3d0a2d3bd.html
转载于:https://www.cnblogs.com/litstrong/archive/2010/05/01/1725713.html
相关资源：数据结构—成绩单生成器