题解——出栈序列统计

题目链接：传送门

描述

栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

输入

就一个数n(1≤n≤15)。

输出

一个数，即可能输出序列的总数目。

样例输入

3

样例输出

5

提示

先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。

用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。

来源

百炼/练习

题解

看提示很重要！照着提示的第二段，用代码翻译一遍就可以！

ps. 关于递归，可以参考之前的文章，我在第一次实验课题解里大致说了一下递归的基本思想

传送门：数据结构与算法——第一节课实验题解

#include<iostream> using namespace std; int cnt=0; // cnt用来记录序列种类数 int n; //递归开始了嗷 void dfs(int l,int c,int r) //左l，中c，右r，参考下面的图解 { if(r==n){ //“出栈元素个数达到n时就计数一次” cnt++; return; //“这也是递归调用结束的条件” } if(l) dfs(l-1,c+1,r); //“如果可以进栈则进一个元素” if(c) dfs(l,c-1,r+1); //“如果可以出栈则出一个元素” } int main() { cin>>n; dfs(n,0,0); //从没有元素入栈开始进行 cout<<cnt; return 0; }

递归细节的图解

对于每种出栈元素没到n的情况，都可以尝试对它进行两种操作，即：

将待入栈元素入栈将栈内元素出栈

这两种操作，每次只能选一个进行，进行后得到一个新的状态，判断它是否是递归终点，如果是则cnt++;然后结束递归，如果不是则将新的状态参数传入，再次重复这一过程。

流程图