题目大意是：
给定一个n，k，表示树上共有n个节点，每个节点最多有k个叶子，问一共多少种摆法，答案对1000000007取模
这里定义一个dp[i]表示 i 个节点对应有多少种方法
f[i][j] 表示一个除去顶点的树中，这个顶点延伸出 j 个子树 ， 这j个子树中共有i 个点
那么只要在f[i][j]上添加一个顶点就得到了 dp[i]
所以dp[i+1] = f[i][0] + f[i][1] ......+f[i][k]
f[i][j] = ∑(f[i-k][j-1]*dp[k]) k<=i;
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define maxn 205 5 const int mod = 1000000007; 6 using namespace std; 7 8 long long dp[maxn],f[maxn][22]; 9 10 int main() 11 { 12 // freopen("a.in" , "r" , stdin); 13 int T,n,k; 14 scanf("%d",&T); 15 while(T--) 16 { 17 scanf("%d%d" , &n , &k); 18 memset(f , 0 , sizeof(f)); 19 memset(dp , 0 , sizeof(dp)); 20 f[0][0] = 1; 21 dp[1] = 1; 22 for(int i=1 ; i<n ; i++){ 23 for(int j=k ; j>=1 ; j--){ 24 for(int t=1 ; t<=i ; t++){ 25 f[i][j] += (f[i-t][j-1]*dp[t])%mod; 26 f[i][j]%=mod; 27 } 28 // cout<<"i: "<<i<<" j: "<<j<<" "<<f[i][j]<<endl;; 29 } 30 31 for(int j=1 ; j<=k ; j++){ 32 dp[i+1] += f[i][j]; 33 dp[i+1]%=mod; 34 } 35 // cout<<"i: "<<i<<" "<<dp[i]<<endl; 36 } 37 printf("%lld\n" , dp[n]); 38 } 39 return 0; 40 }
原文：http://www.cnblogs.com/CSU3901130321/p/4233611.html