经典 DP。
定义 \(f_{i,j}\) 表示 \(i\) 个节点,深度小于等于 \(j\) 的二叉树的个数。
则转移方程为:
\[f_{i,j}=\sum\limits_{k=0}^{i-1}f_{k,j-1}\cdot f_{i-k-1,j-1}
\]
最终答案为 \(f_{n,n}-f_{n,h-1}\)。
复杂度 \(O(n^3)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=40+5;
ll n,h,f[N][N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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<j;++k){
f[j][i]+=f[k][i-1]*f[j-k-1][i-1];
}
}
}
cout<<f[n][n]-f[n][h-1]<<endl;
return 0;
}