题意翻译
用 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;
}