题意

给定固定入栈顺序 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)：

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

代码

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))

复杂度

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

总结

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

一图流解析

保留旧图作为复盘材料。