51nod1412(dp)

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1412

代码：

 1 #include <bits/stdc++.h>
 2 #define MAXN 2010
 3 #define ll long long
 4 using namespace std;
 5 
 6 const int mod=1e9+7;
 7 ll dp[MAXN][20]; //**dp[i][k]表示i个节点高度为k的平衡树的方案数
 8 
 9 int main(void){
10     int n;
11     ll ans=0;
12     cin >> n;
13     dp[0][0]=dp[1][1]=1;
14     for(int i=2; i<=n; i++){
15         for(int k=2; k<=15; k++){
16             for(int j=0; j<i; j++){
17                 dp[i][k]=(dp[i-j-1][k-1]*dp[j][k-1]+dp[i][k])%mod; //左右子树一样高
18                 dp[i][k]=(2*dp[i-j-1][k-1]*dp[j][k-2]+dp[i][k])%mod;//左右子树不一样高，这种情况又分为左子树更高和右子树更高两种情况，但他们的值是一样的
19             }
20         }
21     }
22     for(int i=0; i<=15; i++){
23         ans=(ans+dp[n][i])%mod;
24     }
25     printf("%lld
", ans);
26     return 0;
27 }