数学、卡特兰数、动态规划

设计 $C_n$ 为 $n$ 个元素的出栈序列数量。

使用 $1$ 对所有序列分类，对于第 $i$ 位为 $1$ 的出栈序列，$1 \sim i-1$ 一定在 $1$ 出栈前全部出栈，$i+1 \sim n$ 一定在 $1$ 出栈后入栈并全部出栈。

根据这个事实将 $1 \sim n$ 出栈划分为 $1 \sim i-1$ 和 $i+1 \sim n$ 出栈的两个子问题，得到状态转移方程。

$$C_{0}=1,C_{1}=1$$

$$C_n = \sum\limits_{i=0}^{n-1} C_{i}C_{n-1-i}$$

答案即为卡特兰数 $C_n$，可以 $O(n^2)$ 动态规划求出。

#include<bits/stdc++.h>
using namespace std;
int n,c[20];
int main(){
    scanf("%d",&n);
    c[0]=1,c[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=n-1;j++) c[i]+=c[j]*c[i-1-j];
    printf("%d\n",c[n]);
    return 0;
}