Codeforces 9D 卡特兰数，二叉树种类

题意：

给定$n,h$，求用$n$的结点组成的高度$\ge h$的二叉树有多少种

方法：

TIPS:二叉树计数左右儿子不等价,（x,y)和(y,x)是两种可能（x!=y）

首先先从任意二叉树计数开始，是一个经典的卡特兰数问题，这里利用$dp$来求卡特兰数，设$f[i]$为$i$个结点组成的不同的二叉树种数，那么要求$dp[i]$，先放置根节点，然后就是左右子树有多少种的问题，枚举左子树的大小$j$，有

$$f[i]=\sum _{j=0}^{i-1}f[j]\ast f[i-j-1]$$

那么在这里有一个高度限制，于是添加一维限制高度，设$dp[i][j]$为$i$个结点组成的深度为$j$的二叉树有多少种，要求$dp[i][j]$，同样先枚举左子树大小$k$，此时左子树的大小$h_l$可能$<j-1$或$==j-1$

当$h_l<j-1$，要是最后深度为$j$，那么右子树深度要是$j-1$，于是

$$dp[i][j]=\sum _{k=0}^{i-1}\sum _{l=0}^{j-2}dp[k][l]\ast dp[i-k-1][j-1]$$

当$h_l==j-1$，那么右子树深度不超过$j-1$即可，于是

$$dp[i][j]=\sum _{k=j-1}^{i-1}\sum _{l=0}^{j-1}dp[k][j-1]\ast dp[i-k-1][l]$$

实际上，这两种就是左右子树交换的重复计数，但是不建议并且不能计算一边的$ans$再$\times 2$，当左右子树规模与深度完全一样是，这确实是一种，其他的是两种，并不是所有的计数都要$\times 2$的，而把规模完全一样的计数分离开又添加了难度和空间，不如直接分类讨论。一开始样例一算了个2，问题应该是在开始以为左右儿子等价并且少算了左右规模和深度一样的情况

这样的计数方法更偏向是组合数学，而不是树形$dp$，这是基于卡特兰数的多限制的一种$dp$

#include
#define ll long long
using namespace std;

int n,h;
ll ans,dp[50][50];

int main()
{
    cin>>n>>h;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=j-1;k<=i-1;k++)
            {
                for(int l=0;l<=min(i-k-1,j-1);l++)
                {
                    dp[i][j]+=dp[k][j-1]*dp[i-k-1][l];
                }
            }
            for(int k=0;k<=i-1;k++)
            {
                for(int l=0;l<=j-2;l++)
                {
                    dp[i][j]+=dp[k][l]*dp[i-k-1][j-1];
                }
            }
        }
    }
    ll ans=0;
    for(int i=h;i<=n;i++) ans+=dp[n][i];
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36