题目描述

将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。

思路

出栈方式其实就是一个卡特兰数，用dp公式推就可以了
f[i]表示深度为i的栈出栈方式数
f[i]=f[i-1]*(4*i-2)/(i+1)
O(n)

#include 
int main()
{
    int n;
    long long ans=1;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        ans=ans*(4*i-2)/(i+1);
    printf("%lld\n",ans);
}