M27217: 有多少种合法的出栈顺序

http://cs101.openjudge.cn/practice/27217/

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

宁宁考虑的是这样一个问题：一个操作数序列，1,2,...,n（图示为 1 到 3 的情况），栈 A 的深度大于 n。现在可以进行两种操作，将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1的过程。

（原始状态如上图所示)你的程序将对给定的 n，计算并输出由操作数序列 1,2,...,n 经过操作可能得到的输出序列的总数。

输入

输入文件只含一个整数 n（1 <= n <= 1000）。

输出

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

样例输入

3

样例输出

5

来源：洛谷 1044

python

import sys
from functools import lru_cache
sys.setrecursionlimit(1<<30)

@lru_cache(None)
def dfs(push_remaining, stack_size):
    if push_remaining == 0 and stack_size == 0:
        return 1

    total = 0
    # 操作1: 如果还有数可入栈
    if push_remaining > 0:
        total += dfs(push_remaining - 1, stack_size + 1)
    # 操作2:如果栈非空，可以出栈
    if stack_size > 0:
        total += dfs(push_remaining, stack_size - 1)
    return total

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    print(dfs(n, 0))

python

'''
递归/记忆化搜索，https://www.luogu.com.cn/problem/solution/P1044
1）二维数组f[i,j]，用下标 i 表示队列里还有几个待排的数，j 表示栈里有 j 个数，
f[i,j]表示此时的情况数
2）那么，更加自然的，只要f[i,j]有值就直接返回；
3）然后递归如何实现呢？首先，可以想到，要是数全在栈里了，就只剩1种情况了，所以：i=0时，返回1；
4）然后，有两种情况：一种栈空，一种栈不空：在栈空时，我们不可以弹出栈里的元素，只能进入，
所以队列里的数−1，栈里的数+1，即加上 f[i−1,j+1] ；另一种是栈不空，
那么此时有出栈1个或者进1个再出1个 2种情况，分别加上 f[i−1,j+1] 和 f[i,j−1] 
'''
import sys
sys.setrecursionlimit(1<<30)

def dfs(i, j, f):
    if f[i][j] != -1:
        return f[i][j]
    
    if i == 0:
        f[i][j] = 1
        return 1
    
    if j == 0:
        f[i][j] = dfs(i - 1, j + 1, f)
        return f[i][j]
    
    f[i][j] = dfs(i - 1, j + 1, f) + dfs(i, j - 1, f)
    return f[i][j]

n = int(input())
f = [[-1] * (n + 1) for _ in range(n + 1)]

result = dfs(n, 0, f)
print(result)

这个问题可以通过卡特兰数（Catalan number）来解决。对于一个操作数序列 1, 2, ..., n，经过栈的 push 和 pop 操作得到的输出序列的总数就是第 n 个卡特兰数。卡特兰数的递推公式为：

$C_{n} = {\begin{cases} 1, & n = 0 \\ \sum_{i = 0}^{n - 1} C_{i} C_{n - 1 - i}, & n > 0 \end{cases}$

这表示第 n 个卡特兰数是前 n 个卡特兰数交叉乘积的和。

也可以通过组合数公式来计算：

$C_{n} = \frac{C_{2 n}^{n}}{n + 1} = \frac{(2 n)!}{n! (n + 1)!}$

代码实现（使用递推公式）

python

n = int(input())
# 初始化卡特兰数数组
catalan = [0] * (n + 1)
# 初始化 C_0 为 1
catalan[0] = 1

# 递推计算卡特兰数
for i in range(1, n + 1):
    for j in range(i):
        catalan[i] += catalan[j] * catalan[i - 1 - j]

# 输出第 n 个卡特兰数
print(catalan[n])

卡特兰数（Catalan number）在计算机科学领域有着广泛的应用，下面为你详细介绍一些常见的应用场景：

栈操作相关问题

合法出栈序列计数：给定一个包含 n 个元素的操作数序列 1, 2, ..., n，通过栈的入栈（push）和出栈（pop）操作可以得到不同的输出序列。这些合法的输出序列的总数就是第 n 个卡特兰数。例如，当 n = 3 时，操作数序列为 1, 2, 3，经过栈操作可能得到的输出序列有 1 2 3、1 3 2、2 1 3、2 3 1、3 2 1，共 5 种，这正好是第 3 个卡特兰数的值。
括号匹配问题：对于 n 对括号组成的合法括号序列的数量，同样可以用卡特兰数来计算。合法的括号序列要求在任意位置，左括号的数量总是不少于右括号的数量。例如，当 n = 2 时，合法的括号序列有 (()) 和 ()()，数量为 2，即第 2 个卡特兰数。

二叉树相关问题

不同形态的二叉树计数：给定 n 个节点，可以构造出的不同形态的二叉树的数量是第 n 个卡特兰数。这里只考虑树的拓扑结构，不考虑节点的值。例如，当 n = 3 时，可以构造出 5 种不同形态的二叉树。
例如：24755:有多少种二叉树，http://cs101.openjudge.cn/practice/24755/
二叉搜索树（BST）的数量：对于包含 n 个不同节点的二叉搜索树的数量，也是第 n 个卡特兰数。因为二叉搜索树的中序遍历是有序的，所以不同形态的二叉搜索树的数量与不同形态的二叉树数量相同。

多边形划分问题

凸多边形三角划分：将一个 n + 2 条边的凸多边形通过不相交的对角线划分成三角形的方案数是第 n 个卡特兰数。例如，对于一个五边形（n = 3），可以通过不同的方式用对角线将其划分为三角形，划分方案的总数为 5，即第 3 个卡特兰数。

路径问题

格路径计数：在一个 n × n 的网格中，从左下角 (0, 0) 走到右上角 (n, n)，只能向右或向上走，并且不穿过对角线（即路径上任意点的横坐标总是不小于纵坐标）的路径数量是第 n 个卡特兰数。

表达式组合问题

表达式加括号的方式：对于一个包含 n 个运算符的表达式，通过合理添加括号来确定运算顺序的不同方式的数量是第 n 个卡特兰数。例如，对于表达式 a + b + c + d（有 3 个运算符），添加括号的不同方式有 5 种，对应第 3 个卡特兰数。

综上所述，卡特兰数在计算机科学的多个领域都有重要的应用，它为解决许多计数问题提供了有效的方法。

套数学公式

python

n = int(input())
r = 1
for i in range(1, n+1):
    r = r * (n + i)
    r = r // i  # 整数安全写法，除法放在每步末尾
r = r // (n + 1)
print(r)

“循环累乘”计算组合数
python
r = 1
for i in range(1, n+1):
    r = r * (n + i) // i
就能计算出 $(\binom{2 n}{n}) = \frac{(2 n)!}{n!, n!}$
💡 一、目标：计算组合数
定义：
$(\binom{2 n}{n}) = \frac{(2 n)!}{n! \cdot n!}$
直接算阶乘很容易溢出或效率低，我们想让它一步步地乘除计算，避免中间结果太大。
🧮 二、化简展开
把上式拆成分子分母：
$(\binom{2 n}{n}) = \frac{(2 n) (2 n - 1) (2 n - 2) \dots (n + 1)}{n!}$
也就是上半部分的 n 个连续整数相乘，再除以下半部分的 n!。
🔁 换一种写法：
我们可以把分子每一项对应地写成：
$\prod_{i = 1}^{n} \frac{n + i}{i}$
因为当 i 从 1 到 n 时：
i n+i 分数项
1 n+1 (n+1)/1
2 n+2 (n+2)/2
3 n+3 (n+3)/3
... ... ...
n 2n (2n)/n
相乘起来就是： $\frac{(n + 1) (n + 2) \dots (2 n)}{1 \cdot 2 \dots n} = \frac{(2 n)!}{n!, n!}$
这就是组合数 $(\binom{2 n}{n})) ！$
🧰 三、用循环计算
我们不能直接写分数乘法，所以在 Python 里就写成：
python
r = 1
for i in range(1, n+1):
    r = r * (n + i) // i

i	n+i	分数项
1	n+1	(n+1)/1
2	n+2	(n+2)/2
3	n+3	(n+3)/3
...	...	...
n	2n	(2n)/n

直接使用“标准”Catalan公式

python

import math
def catalan(n):
    if n==0 or n==1:
        return 1
    else:
        return math.comb(2*n,n)//(n+1)
n=int(input())
print(catalan(n))

用“组合差”形式实现

python

from math import factorial as f
n = int(input())
print(f(2 * n) // (f(n) ** 2) - f(2 * n) // f(n - 1) // f(n + 1))

两者等价性证明

我们验证： $(\binom{2 n}{n}) - (\binom{2 n}{n + 1}) = \frac{1}{n + 1} (\binom{2 n}{n})$

因为： $\frac{(\binom{2 n}{n + 1})}{(\binom{2 n}{n})} = \frac{n}{n + 1}$

所以： $(\binom{2 n}{n}) - (\binom{2 n}{n + 1}) = (\binom{2 n}{n}) (1 - \frac{n}{n + 1}) = \frac{1}{n + 1} (\binom{2 n}{n})$

这个题目挺好的，可以 dfs+lru_cache, dp, 或者利用两种 catalan公式直接计算。而且直接计算时候，还要注意整数安全问题（避免浮点数精度问题）。如果直接用math.comb，可以避免浮点数问题。M27217:有多少种合法的出栈顺序，http://cs101.openjudge.cn/pctbook/M27217/

思路：可以利用卡特兰数的数学规律来求解。该问题的本质是，给定操作数序列 1,2,…,n，通过栈的 push 和 pop 操作能生成的不同输出序列总数，恰好等于第 n 个卡特兰数。

卡特兰数的递推公式为：

(C_0 = 1)，(C_{n+1} = \frac{4n+2}{n+2} \times C_n)（或等价递推式 (C_n = \frac{4n-2}{n+1} \times C_{n-1})）

对于本题，我们可以通过递推的方式计算第 n 个卡特兰数，从而得到可能的输出序列总数。

代码：

python

n = int(input())
catalan = 1
for i in range(1, n + 1):
    catalan = catalan * (4 * i - 2) // (i + 1)
print(catalan)

思路：答案为大名鼎鼎的卡塔兰数。这里是用动态规划法解决的，假设最后一个出栈的元素是 $k$ ，那么在它入栈之前比它小的 $k - 1$ 个元素均已出栈，在它入栈之后比它大的 $n - k$ 个元素才入栈并都先于它出栈，则卡塔兰数 $C_{n} = \sum_{k} C_{n - k} C_{k - 1}$

python

def catalan(n: int):
    catalans = [1] * (n + 1)
    if n <= 1:
        return 1
    for i in range(2, n + 1):
        catalans[i] = 0
        for k in range(1, i + 1):
            catalans[i] += catalans[i - k] * catalans[k - 1]
    return catalans[n]

n = int(input())
print(catalan(n))

思路：一开始用回溯与双栈的解法超时了，接着才想到可以利用dp的方法化简（且这题只需要求数量而不是每种情况的具体排序）。 $d p [i] [j]$ 为已经出栈了 i 个元素，栈内还有 j 个元素时的方案数。若栈非空可以执行pop操作，得到 $d p [i + 1] [j - 1] + = d p [i] [j]$ ；若还要数字可以入栈可以执行push操作，即 $d p [i] [j + 1] + = d p [i] [j]$ 。通过递推最终得到 $d p [n] [0]$ 的结果。

python

n = int(input())
dp = [[0] * (n + 2) for _ in range(n + 2)]
dp[0][0] = 1

for i in range(n + 1):
    for j in range(n + 1):
        if i == n and j == 0:
            continue
        if j > 0:
            dp[i+1][j-1] += dp[i][j]
        if i + j < n:
            dp[i][j+1] += dp[i][j]

print(dp[n][0])

M27217: 有多少种合法的出栈顺序 ​

M27217: 有多少种合法的出栈顺序