$dp$。
设$dp[i][j]$表示包含$i$个节点的最后一层有$j$个节点的树有多少种。
递推很简单，如果$j\% k = = 0$，那么$dp[i][j]$就要加上$dp[i-j][k]$的方案。
本地跑大约$500-600ms$左右的时间就可以打完表了，$sumbit$发现跑了$900$多$ms$。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; int dp[1005][1005],ans[1005]; int mod=1e9+7; int main() { dp[1][1]=1; ans[1]=1; for(int i=2;i<=1000;++i) { for(int j=1;j<=i-1;++j) { for(int k=1;k<=j;++k) { if(j%k==0) dp[i][j]=(dp[i][j]+dp[i-j][k])%mod; } ans[i]=(ans[i]+dp[i][j])%mod; } } int cas=1,n; while(scanf("%d",&n)!=EOF) { printf("Case %d: %d\n",cas++,ans[n]); } return 0; }
原文：http://www.cnblogs.com/zufezzt/p/5816106.html