[NOIP 2003 普及组] 栈

题意

给定固定入栈顺序 1..n，每次可以把下一个数入栈，也可以把栈顶元素弹出到输出序列。问可能得到多少种不同输出序列。

思路

具体栈里有哪些数并不重要。因为入栈顺序固定，后续可操作数量只由两个状态决定：

waiting：还有多少个数没有入栈；
stack_size：当前栈里有多少个数。

定义 count_outputs(waiting, stack_size) 表示从这个状态出发的方案数。

转移：

如果 waiting > 0，可以入栈：(waiting-1, stack_size+1)；
如果 stack_size > 0，可以出栈：(waiting, stack_size-1)。

当 waiting == 0 时，剩下只能一直出栈，方案数为 1。

小 DP 表

以 n=3 为例，答案为 f(3,0)：

状态	方案数含义
`f(0, k)`	没有数可入栈，只能全部弹出，值为 `1`
`f(1, 0)`	只能先入栈，再弹出，值为 `1`
`f(2, 0)`	对应 `n=2` 的输出方案，值为 `2`
`f(3, 0)`	对应样例 `n=3`，值为 `5`

Python 知识

@lru_cache(None) 可以给递归函数自动加记忆化缓存。
递归函数的参数必须能哈希，整数参数天然适合做缓存键。
Python 大整数可以直接保存 Catalan 数结果。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16from functools import lru_cache


@lru_cache(None)
def count_outputs(waiting, stack_size):
    if waiting == 0:
        return 1

    answer = count_outputs(waiting - 1, stack_size + 1)
    if stack_size > 0:
        answer += count_outputs(waiting, stack_size - 1)
    return answer


n = int(input())
print(count_outputs(n, 0))

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 14:56
 * update_at: 2026-08-14 14:56
 */
#include <iostream>

const int max_n = 20;

int n;
long long memo[max_n][max_n];  // memo[pushed][popped]，-1 表示还没算过

// 已经入栈 pushed 个、出栈 popped 个时，还有多少种方式把剩下的数全部出栈
long long dfs(int pushed, int popped) {
    if (popped == n) {
        return 1;  // 所有数都已出栈，这是唯一一种完成方式
    }
    if (memo[pushed][popped] != -1) {
        return memo[pushed][popped];
    }
    long long total = 0;
    if (pushed < n) {
        total += dfs(pushed + 1, popped);  // 把下一个数入栈
    }
    if (popped < pushed) {
        total += dfs(pushed, popped + 1);  // 栈里有数，弹出一个
    }
    memo[pushed][popped] = total;
    return total;
}

int main() {
    std::cin >> n;
    for (int pushed = 0; pushed <= n; pushed += 1) {
        for (int popped = 0; popped <= n; popped += 1) {
            memo[pushed][popped] = -1;  // 初始都标记为"还没算过"
        }
    }
    std::cout << dfs(0, 0) << '\n';
    return 0;
}

复杂度

状态数量为 $O(n^2)$ ，每个状态计算一次，时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。

总结

栈内具体元素可以被“当前栈大小”代替，这是本题从搜索变成 DP 的关键。

一图流解析

保留旧图作为复盘材料。

[NOIP 2003 普及组] 栈

目录

题意

思路

小 DP 表

Python 知识

代码

Guide 风格代码

复杂度

总结

一图流解析