n结点的树形态的数目等于
n-1个结点分配到两个子树的个数之积。
5结点树形态的数目就是 抽出一个点做根结点
其余子树 也就是 (4)*(0) (3)*(1) (2)*(2) (1)*(3) (0)*(4)
dp[x] 等于x个结点的树形态数目
//抽出一个点做根结点
dp[x] = dp[x-1]*dp[0] + dp[x-2]*dp[1] ~~~~~ dp[0]*dp[x-1];
代码如下
#include <iostream>
#include <memory.h>
using namespace std;
/*
https://www.acwing.com/problem/content/3694/
求 N个结点能够组成的二叉树的个数。
输入格式
一个整数 N。
输出格式
输出能组成的二叉树的个数。
数据范围
1≤N≤20
输入样例:
3
输出样例:
5
*/
const int N = 22;
long long dp[N];
int n;
long long dpfunc(int x) {
if (dp[x] != -1) return dp[x];
long long& v = dp[x];
v = 0;
for (int i = 0; i < x; i++) {
v += dpfunc(i) * dpfunc(x-1 - i);
}
return v;
}
int main()
{
cin >> n;
memset(dp,-1,sizeof dp);
dp[0] = 1; dp[1] = 1; dp[2] = 2;
cout << dpfunc(n) << endl;
return 0;
}
# 牛啊,直接看到你的题解,咻咻咻
牛逼