【GESP/CSP练习】GESP四级 / CSP-J 题解：luogu-P1044 [NOIP2003 普及组] 栈

NOIP 2003 普及组第三题，洛谷 P1044。本题是算法竞赛与计算机等级考试中极为经典的卡特兰数（Catalan Number）与递推计数模型启蒙代表作，标准收录于 CCF GESP 四级考纲（简单递归与递推初步考点）以及 CSP-J 普及组核心递推必做题单。题目核心考察如何将计算机基本数据结构“栈”的合法操作序列抽象为组合计数问题，通过“最后一个出栈元素”的完备划分推导出卡特兰数经典卷积递推关系式，或者从操作步骤出发构建二维状态递推，实现高效精确求解。题目难度⭐☆☆☆☆，洛谷难度等级评定为普及-。

luogu-P1044 [NOIP2003 普及组] 栈

🔗 洛谷原题传送门：luogu-P1044 [NOIP2003 普及组] 栈

题目描述

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

现在可以进行两种操作，

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

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

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

输入格式

输入文件只含一个整数 $n$ （ $1 \le n \le 18$ ）。

输出格式

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

输入输出样例

输入 #1

Code 1 行

13
2

输出 #1

Code 1 行

15
2

说明/提示

样例 1 解释

对于输入 $n = 3$ ，初始序列为 $1, 2, 3$ 。合法的出栈序列共有 $5$ 种，分别为：

$1, 2, 3$ （push 1, pop 1, push 2, pop 2, push 3, pop 3）
$1, 3, 2$ （push 1, pop 1, push 2, push 3, pop 3, pop 2）
$2, 1, 3$ （push 1, push 2, pop 2, pop 1, push 3, pop 3）
$2, 3, 1$ （push 1, push 2, pop 2, push 3, pop 3, pop 1，即题面配图所示过程）
$3, 2, 1$ （push 1, push 2, push 3, pop 3, pop 2, pop 1）

注：序列 $3, 1, 2$ 是不可能通过合法入栈出栈得到的，因为若 $3$ 第一个出栈，说明 $1, 2, 3$ 均已入栈，此时栈顶必须是 $2$ ，不可能先弹出 $1$ 。因此总方案数为 $5$ 。

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 18$ 。

题目深度剖析

1. 问题本质与数学建模

本题表面上考察的是数据结构“栈”的先进后出（LIFO）操作模拟，但题目并不要求我们输出所有具体的出栈排列，而是询问可能得到的合法出栈序列的总数。这是一个纯粹的组合计数与递推建模问题。

为了理清状态关系，我们需要找到一个能够将规模为 $n$ 的大问题，不重不漏地拆解为更小规模子问题的“划分基准”。

在所有的合法出栈序列中，原本的操作数 $1, 2, \dots, n$ 最终都必然要出栈。我们聚焦于最后一个出栈的数是谁：

设元素 $k$ （ $1 \le k \le n$ ）是整个序列中最后离开栈的那个数；
既然 $k$ 是最后一个出栈的数，那么在 $k$ 进栈之后、直到 $k$ 最终出栈出栈之前，其余所有的数都必须完成各自的进栈与出栈全过程；
又因为操作数是严格按照 $1, 2, \dots, n$ $1, 2, \dots, n$ 的顺序依次由队列头端送入栈中：
1. 所有比 $k$ 先进栈的数是 $1, 2, \dots, k - 1$ ，共 $k - 1$ 个数。它们必须在 $k$ 最终出栈之前就已经全部出栈并进入输出序列；
2. 所有比 $k$ 后进栈的数是 $k + 1, k + 2, \dots, n$ ，共 $n - k$ 个数。它们在 $k$ 进栈之后才依次进栈，并且必须在 $k$ 最终出栈之前全部出栈完毕。

因此，当确定了元素 $k$ 是最后一个出栈的元素时：

前 $k - 1$ 个元素自身的进出栈过程构成一个独立的子问题，方案数为 $h(k - 1)$ ；
后 $n - k$ 个元素自身的进出栈过程同样构成一个独立的子问题，方案数为 $h(n - k)$ ；
这两个子问题在时间与逻辑上是完全解耦且独立的。根据数学中的乘法原理，以 $k$ 为最后一个出栈元素的总方案数为： $h(k - 1) \times h(n - k)$

因为元素 $k$ 可以是 $1, 2, \dots, n$ 中的任意一个，并且以不同元素作为最后一个出栈元素的方案集互不相交（互斥），根据数学中的加法原理，将所有可能的 $k$ 对应的方案数求和，即可得到长度为 $n$ 的出栈序列总数： $h(n) = \sum_{k=1}^{n} h(k - 1) \times h(n - k)$

令变量代换 $j = k - 1$ ，当 $k$ 从 $1$ 遍历到 $n$ 时， $j$ 从 $0$ 遍历到 $n - 1$ ，上式可标准写作： $h(n) = \sum_{j=0}^{n-1} h(j) \times h(n - 1 - j)$

这就是离散数学与计算机科学中最著名的数列之一——**卡特兰数（Catalan Number）**的标准卷积递推关系式！

2. 卡特兰数的边界与前几项验证

卡特兰数的边界条件约定如下：

$h(0) = 1$ ：空序列对应 $0$ 个元素的栈操作，唯一的一种合法状态（不进行任何操作）；
$h(1) = 1$ ：只有一个元素，直接进栈后出栈，方案数为 $1$ 。

利用卷积递推式逐步手动推导前几项：

$n = 2$ ： $h(2) = h(0)h(1) + h(1)h(0) = 1 \times 1 + 1 \times 1 = 2$ （合法序列：1 2、2 1）
$n = 3$ ： $h(3) = h(0)h(2) + h(1)h(1) + h(2)h(0) = 1 \times 2 + 1 \times 1 + 2 \times 1 = 2 + 1 + 2 = 5$ （与样例输出完全一致！）
$n = 4$ ： $h(4) = h(0)h(3) + h(1)h(2) + h(2)h(1) + h(3)h(0) = 1 \times 5 + 1 \times 2 + 2 \times 1 + 5 \times 1 = 14$

3. 算法演进：两种递推思维的碰撞

在 CCF GESP 四级（简单递推）与 CSP-J 学习阶段，掌握多角度建模有助于深入理解动态规划与递推的真谛。对于本题，存在两种经典的解法模型：

视角一：一维卡特兰数卷积递推（推荐解法）

核心思路：直接利用上述推导出的卡特兰数递推式 $h(i) = \sum_{j=0}^{i-1} h(j)h(i - 1 - j)$ 。
实现方式：自底向上双层循环递推，外层 $i$ 从 $2$ 到 $n$ ，内层 $j$ 从 $0$ 到 $i - 1$ ，累乘求和。
优势：逻辑凝练，空间占用仅为 $\mathcal{O}(n)$ ，代码量极少，是考场上的首选武器。

视角二：二维状态记忆化递推 / 动态规划

核心思路：从栈的操作过程状态出发进行建模。
状态定义：设 $dp(i, j)$ 表示当前待入栈队列中还有 $i$ 个数，且栈内部当前存有 $j$ 个数时的后续合法出栈序列总数。
状态转移：
- 若栈为空（ $j = 0$ ），此时无法进行出栈操作，必须执行入栈操作：待入栈数减 $1$ ，栈内数加 $1$ ，即 $dp(i, 0) = dp(i - 1, 1)$ ；
- 若栈非空（ $j > 0$ ），此时既可以执行入栈（需满足 $i > 0$ ），也可以执行出栈： $dp(i, j) = dp(i - 1, j + 1) + dp(i, j - 1)$
边界条件：当队列中已无待入栈元素（ $i = 0$ ）时，栈中剩余的 $j$ 个元素只能唯一按自顶向下顺序依次弹出，方案数固定为 $1$ ，即对所有 $j \ge 0$ 均有 $dp(0, j) = 1$ 。
目标解：初始状态为 $n$ 个元素待入栈、栈为空，即 $dp(n, 0)$ 。

递推方案	建模视角	状态定义	时间复杂度	空间复杂度	适用场景
一维卡特兰卷积递推	宏观数学划分（最后出栈元素）	$h[i]$ 表示规模为 $i$ 时的出栈方案数	$\mathcal{O}(n^2) \approx 324$ 次计算	$\mathcal{O}(n)$ 一维数组	推荐解法，代码极简，速度极快
二维状态网格递推	微观操作模拟（push/pop 决策）	$dp[i][j]$ 表示待入栈 $i$ 个、栈内 $j$ 个	$\mathcal{O}(n^2)$ 矩阵递推	$\mathcal{O}(n^2)$ 二维数组	直观展示状态机转移，教学意义高

在题目给定的数据范围 $n \le 18$ 下，两种方法均在不到 $1$ 毫秒内瞬时出解，洛谷评测均为最优满分（100 分 AC）。

4. 数据范围与整型边界考量

题目保证 $1 \le n \le 18$ ；
经计算，第 $18$ 项卡特兰数为： $h(18) = 477638700 \approx 4.77 \times 10^8$
标准 32 位有符号整型 int 的最大取值范围为 $2^{31} - 1 = 2147483647 \approx 2.14 \times 10^9$ ；
虽然 $h(18)$ 未超过 int 上限，但乘法累加过程中若涉及更高项（例如 $n = 19$ 时 $h(19) = 1767263190$ ， $n = 20$ 时 $h(20) = 6564120420$ 就会彻底爆 int）。
遵循竞赛规范与 CCF 优良习惯，计数类问题统一采用 64 位整型 long long 存储状态数组，彻底消除整型溢出风险。

5. 常见考场避坑点

切勿遗漏 $h(0) = 1$ 的边界初值：
- 很多初学者误以为“没有元素就是 $0$ 种方案”，从而赋初值 $h(0) = 0$ ；
- 一旦 $h(0) = 0$ ，根据卷积公式 $h(2) = h(0)h(1) + h(1)h(0) = 0$ ，会导致后续所有项全为 $0$ ！在组合数学中，空集的方案数定义为 $1$ 。
严禁使用局部变长数组（VLA）：
- 不要在 main() 函数内部编写 long long h[n + 1];，这在 C++11 标准与 GESP 官方机考环境下严禁使用；
- 规范做法是在全局数据区声明固定大小的静态常量数组 const int MAXN = 25; long long h[MAXN];。
保持输入输出简洁标准：
- 无需引入繁杂的快读加速模板，直接使用标准 cin >> n; 与 cout << h[n] << endl; 即可。

完整参考代码 (C++11)

C++ 44 行

1/**
2 * Problem: luogu-P1044 [NOIP2003 普及组] 栈
3 * Algorithm: 卡特兰数 (Catalan Number) / 卷积递推 (Recurrence)
4 * Standard: C++11 (CCF GESP 官方大纲规范)
5 * Author: OneCoder
6 */
7
8#include <iostream>
9
10using namespace std;
11
12// 数据规模：保证 1 <= n <= 18
13// h[i] 表示含有 i 个元素的操作数序列，经过合法的进栈、出栈操作后可能得到的出栈序列总数（即第 i 项卡特兰数）
14// 当 n = 18 时，h[18] = 477638700，在 32 位整型范围内，但为防止乘法溢出及遵循规范统一采用 long long
15const int MAXN = 25;
16long long h[MAXN];
17
18int main() {
19    int n;
20    // 直接读入操作数序列长度 n
21    cin >> n;
22
23    // 边界初始化：
24    // 0 个元素（空状态）方案数为 1，1 个元素只有 1 种出栈可能
25    // 注意：h[0] 必须初始化为 1，否则后续卷积乘积项将全部退化为 0
26    h[0] = 1;
27    h[1] = 1;
28
29    // 自底向上递推计算卡特兰数 h[2] 到 h[n]
30    // 状态转移方程：h[i] = sum_{j=0}^{i-1} (h[j] * h[i - 1 - j])
31    // 物理意义：枚举第 (j + 1) 个元素作为整个序列中“最后一个出栈”的元素，
32    // 其前半部分 j 个元素与后半部分 (i - 1 - j) 个元素各自独立构成子卡特兰序列
33    for (int i = 2; i <= n; ++i) {
34        h[i] = 0; // 初始化当前状态累计和
35        for (int j = 0; j < i; ++j) {
36            h[i] += h[j] * h[i - 1 - j];
37        }
38    }
39
40    // 输出包含 n 个数时所有可能的出栈序列总数目
41    cout << h[n] << endl;
42
43    return 0;
44}
45