# ~~动态转移方程是啥~~
by t162 @ 2019-03-25 17:53:51
```
#include<bits/stdc++.h>
using namespace std;
long long a,b[21];
int main()
{
scanf("%lld",&a);
b[0]=1;
b[1]=1;
for(int i=2;i<=a;i++)
{
b[i]=b[i-1]*(4*i-2)/(i+1);
}
printf("%lld",b[a]);
}
```
by 樱雪喵 @ 2019-08-11 10:44:04
我来给你解答
这个题有二维递推和一维递推两种方法
二维递推很好理解，你就理解成一个整数集合可构成的二叉查找树的数目：
$f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0)$，$f(0)=1$。
一维递推需要用到通项公式：$f(n)=C_{2n}^n$（组合数）
由组合数公式$C_{2n}^n=(2n)!/(n!n!)$，$C_{2n-2}^{n-1}=(2n-2)!/((n-1)!(n-1)!)$，手推一下就得到$C_{2n}^n=C_{2n-2}^{n-1}*(4n-2)/n$。
by wancong @ 2020-01-15 23:33:56