P1044 栈（卡特兰数）

以你之姓@ 2023-02-17 03:44 14阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200612084951448.png]  
题目背景  
栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述  
宁宁考虑的是这样一个问题：一个操作数序列，1,2,\\ldots ,n1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 nn。

现在可以进行两种操作，

将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）  
将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）  
使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

**解题思路**：卡特兰数的应用。  
出栈次序  
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? \[4-5\]

常规分析  
首先，我们设f（n）=序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)\*f(k-1)种，求和便是Catalan递归式。ps.author.陶百百）  
首次出空之前第一个出栈的序数k将1n的序列分成两个序列，其中一个是1k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。  
此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。  
看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n-1）（n=0，1，2，……）。  
最后，令f（0）=1，f（1）=1。  
[详细解析][Link 1]

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    int f[20];
    int main()
    { 
       ios::sync_with_stdio(0),cin.tie(0);
       int i,n,j;
       cin>>n;
       f[0]=1,f[1]=1;
       for(i=2;i<=n;i++)
       { 
       	for(j=1;j<=n;j++)
       	f[i]+=f[j-1]*f[i-j];
       }
       cout<<f[n];
       return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200612085040952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1Mjc2NQ==,size_16,color_FFFFFF,t_70
[20200612084951448.png]: https://img-blog.csdnimg.cn/20200612084951448.png
[Link 1]: https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin