题意

问 $n$ 个点组成的二叉树高度大于 $h$ 的有多少个。

题解

设状态为 $dp[n][h]$ 表示 $n$ 个点深度不超过 $h$ 的二叉树数量，那么答案即为 $dp[n][h]-dp[n][h-1]$。

考虑转移：

$dp[n][h]=\sum_{i=1}^ndp[i][h-1]\times dp[n-i-1][h-1]$

让后我们设置初始状态为：$dp[i][0]=0, dp[0][i]=1$ 。

转移的含义很显然，就是左边所有 $h-1$ 的方案和右边所有 $h-1$ 相匹配然后多了父亲所以深度加一。

代码

#include<cstdio>
long long f[37][37];
int main() {
	int n,h;
	scanf("%d%d",&n,&h);
	for(int i=0;i<=n;++i)	//初始化
		f[0][i]=1;
	for(int i=1;i<=n;++i)		//枚举高度
		for(int j=1;j<=n;++j)		//枚举节点
			for(int k=0;k<j;++k)		//枚举左右子树节点
				f[j][i]+=f[k][i-1]*f[j-k-1][i-1];
	printf("%I64d",f[n][n]-f[n][h-1]);
	return 0;
}