73 lines
1.3 KiB
C++
73 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
// 精解讲解
|
||
// https://www.bilibili.com/video/BV1nE411A7ST?from=search&seid=2618099886973795159
|
||
//卡特兰数列原理及应用
|
||
int catalan(int n) {
|
||
if (n == 1)return 1;
|
||
if (n == 2)return 1;
|
||
int res = 0;
|
||
for (int i = 1; i <= n - 1; i++) {
|
||
res += catalan(i) * catalan(n - i);
|
||
}
|
||
return res;
|
||
}
|
||
|
||
|
||
//动态规划版本的卡特兰数
|
||
vector<int> dp;
|
||
|
||
void catalanDp(int n) {
|
||
dp.push_back(1);
|
||
dp.push_back(1);
|
||
for (int i = 2; i <= n; i++) {
|
||
int temp = 0;
|
||
for (int j = 0; j < i; j++) {
|
||
temp += dp[j] * dp[i - j - 1];
|
||
}
|
||
dp.push_back(temp);
|
||
}
|
||
}
|
||
|
||
|
||
//测试函数
|
||
int main() {
|
||
int n = 10;
|
||
for (int i = 1; i <= n; i++)
|
||
cout << catalan(i) << endl;
|
||
|
||
cout << endl;
|
||
|
||
catalanDp(10);
|
||
for (int i = 1; i <= n; i++)
|
||
cout << dp[i - 1] << endl;
|
||
cout << endl;
|
||
return 0;
|
||
}
|
||
|
||
//卡特兰数的例题
|
||
|
||
// 画二叉树问题
|
||
// 扩号匹配
|
||
// 电影院买票 (没有零钱可以找问题)
|
||
// 分割图形
|
||
// 栈的序列 有多少进栈出栈序列
|
||
/**
|
||
*
|
||
1
|
||
1
|
||
2
|
||
5
|
||
14
|
||
42
|
||
132
|
||
429
|
||
1430
|
||
4862
|
||
*/
|
||
//TODO
|
||
// 看裴老师的练习题讲解，LUOGU的试题
|
||
// https://www.bilibili.com/video/BV1nE411A7ST?p=4
|
||
// 讲的太好，不学习太浪费了
|