树形dp
%%%popoqqq
设dp[i][j]表示当前i个节点的树，深度小于等于j的树的个数
那么dp[i][j] = sigma(dp[k][j-1]*dp[n-k-1][j-1]) 比较好理解 然后记忆化搜索就行了
这个dp状态感觉挺巧妙的，以前没见过
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; const int N = 610, mod = 1000000007; int n, h, T; ll dp[N][N]; ll dfs(int n, int h) { if(n < 0 || h < 0) return 0; if(n == 0) return 1; if(h == 0) return n == 1; if(dp[n][h] != -1) return dp[n][h]; ll ret = 0; for(int i = 0; i < n; ++i) ret = (ret + dfs(i, h - 1) * dfs(n - i - 1, h - 1)) % mod; return dp[n][h] = ret; } int main() { memset(dp, -1, sizeof(dp)); for(cin >> T; T; --T) { cin >> n >> h; cout << ((dfs(n, h) - dfs(n, h - 1)) % mod + mod) % mod << endl; } return 0; }
原文：http://www.cnblogs.com/19992147orz/p/7516636.html
