题意翻译
用 n个点组成二叉树,问高度大于等于 h 的有多少个。
输入n和h
解题思路 :
这道是一道dp题,看了题解,思路是问的什么dp转移的方程就是什么,那么我们设成考虑i个节点的子树,高度不大于j的方案数,最后可以通过容斥原理求出答案,答案就是f[n][n]-f[n][h-1]
初始化:当节点为空的时候方案数为1,
f[0][i]=1;
代码:

#include<iostream>
#include<cstring>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=40;
ll f[N][N];//一共包含i个节点,高度小于等于j的树的方案数量
int main()
{
   
	f[1][0]=0;
	int n,h;
	cin>>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<=i-1;k++)
		f[i][j] +=f[k][j-1]*f[i-k-1][j-1];
	for(int i=1;i<=n;i++)
		cout<<f[1][i]<<endl;
	cout<<f[n][n]-f[n][h-1]<<endl;
}