题目描述

关系

415. 栈 - AcWing题库

内容

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

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

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。

宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

宁宁考虑的是这样一个问题：一个操作数序列，从 $1，2$，一直到 $n$，栈 $A$ 的深度大于 $n$。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 $push$ 操作）。
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 $pop$ 操作）。

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列。

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

输入格式

输入文件只含一个整数 $n$。

输出格式

输出文件只有一行，即可能输出序列的总数目。

数据范围

$1\le n\le 18$

输入样例：

3

输出样例：

5

问题分析

思路分析

我们以最后一个出栈的数作为分类讨论的依据，如果最后一个出栈的数为 k，那么比 k 早入栈的数有 k - 1 个，比 k 晚入栈的数有 n - k 个。所以前 k - 1 个数的出栈序列和后面 n - k 的数的出栈序列是子问题，于是我们就可以写出以下递推式：
假设 ${\displaystyle G(k,n)}$ 为 k 是最后一个出栈的数，序列的长度为 n，${\displaystyle F(n)}$ 为长度为 n 的入栈序列的总个数：

这就是卡特兰数的递推式，于是我们可以直接使用公式法。

由于 n 很小，所以我们直接用 dp 求出即可。
定义 f[i]：长度为 i 的输出序列的总数。

显然 f[1] = f[0] = 1。

为什么前 k - 1 个数和后 n - k 个数是子序列呢？第 k 个数是最后一个弹出序列，这就意味着 k 入栈后就一定处于栈底，所以，前 k - 1 个数都已经弹出栈了，与 k 无关；后 n - k 个数一定为 k 的上面，所以也与 k 无关。所以，这两堆数一定是独立的。

拓展

0096-unique-binary-search-trees

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 25;
int n;
int f[N];

int main()
{
    cin >> n;
    
    f[0] = f[1] = 1;
    
    for (int i = 2; i <= n; i++) // 枚举长度
        for (int k = 1; k <= i; k++) // 枚举哪个是最后一个出栈
            f[i] += f[k - 1] * f[i - k];
            
    cout << f[n];
}