公司门户网站设计,做网站用的图片,自己做儿童衣服教程的网站,金城武重庆森林经典台词文章目录 1. 题目描述2. 我的尝试1. 卡特兰数2. 动态规划 1. 题目描述
求 N 个结点能够组成的二叉树的个数。
输入格式 一个整数 N 。 输出格式 输出能组成的二叉树的个数。 数据范围 1 ≤ N ≤ 20 1≤N≤20 1≤N≤20
输入样例
3输出样例
52. 我的尝试
1. 卡特兰数
直接… 文章目录 1. 题目描述2. 我的尝试1. 卡特兰数2. 动态规划 1. 题目描述
求 N 个结点能够组成的二叉树的个数。
输入格式 一个整数 N 。 输出格式 输出能组成的二叉树的个数。 数据范围 1 ≤ N ≤ 20 1≤N≤20 1≤N≤20
输入样例
3输出样例
52. 我的尝试
1. 卡特兰数
直接代公式 r e s C 2 n n ( n 1 ) res \frac {C_{2n}^n} {(n1)} res(n1)C2nn
#include bits/stdc.husing namespace std;int main()
{int n;double res 1;cin n;for (int i 1; i n; i)res res * (i n) / i;cout (unsigned long long int)res / (n 1);return 0;
}
2. 动态规划
#include bits/stdc.h
using namespace std;int main(){int n;cin n;long long data[n1];data[0] 1;data[1] 1;for (int i2; in; i){long long sum 0, l;for (int r 0; r i - 1; r ){l i - r - 1;sum data[r] * data[l];}data[i] sum;}printf(%lld\n, data[n]);return 0;
}
