题解：P1044 [NOIP 2003 普及组] 栈
Doraeman
·
·
题解
提示
我们可以计算多个不同的 n，通过观察找规律可得，这道题的答案符合卡特兰数的规律。
卡特兰数
卡特兰数是组合数学中一种常出现于各种计数问题中的数列。
卡特兰数的前几项为（从第 0 项开始）：
卡特兰数的 $C_n$ 的递推规律是：
$$C_{n}=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_1+C_{n-1}C_0$$。
根据上面这个递推公式，直接写代码即可。
## 代码
### 递推写法
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL C[25];
int main(){
int n; cin >> n;
C[0] = 1;
for(int i=1; i<=n; i++)
for(int j=0; j<i; j++)
C[i] += C[j] * C[i-j-1];
// 递推公式
cout << C[n];
}
```
### 递归写法
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL C(int x){
if(x == 0) return 1;
LL ans = 0;
for(int i=0; i<x; i++)
ans += C(i) * C(x-i-1);
// 递推公式
return ans;
}
int main(){
int n; cin >> n;
cout << C(n);
}
```
## 打表
当然，在我们知道答案的规律之后，也可以在网上搜索卡特兰数的前几项，然后直接**打表**得到答案。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans[] = {1, 1, 2, 5, 14, 42,
132, 429, 1430, 4862, 16796,
58786, 208012, 742900, 2674440,
9694845, 35357670, 129644790, 477638700};
// 刚好到第 18 项
int main(){
int n; cin >> n;
cout << ans[n];
}
```