You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

73 lines
1.3 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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
// 讲的太好,不学习太浪费了