记忆化搜索版本，（故意注释掉查表剪枝，就会让最后一个测试点超时TLE）

#include <iostream>
#include <algorithm>

using namespace std;

// mem[i][j] 用来记录当队列剩余 i 个，栈内有 j 个时的方案数
// 使用 long long 防止运算过程中溢出（虽然 n=18 时 int 其实够用）
long long mem[20][20]; 
int n;

// x: 队列中剩余待入栈的个数
// y: 栈中当前的个数
long long dfs(int x, int y) {
    // 递归边界：如果队列里没数了 (x==0)，剩下的步骤只有一种：
    // 就是把栈里的 y 个数依次弹出来。所以返回 1。
    if (x == 0) return 1;
    
    // 如果这个状态之前算过了，直接返回，避免重复计算
    //if (mem[x][y] != 0) return mem[x][y];  
    
    long long count = 0;
    
    // 选择1: 进栈 (前提是队列里还有数)
    if (x > 0) {
        count += dfs(x - 1, y + 1);
    }
    
    // 选择2: 出栈 (前提是栈里有数)
    if (y > 0) {
        count += dfs(x, y - 1);
    }
    
    // 记录结果并返回
    return mem[x][y] = count;
}

int main() {
    cin >> n;
    // 从队列剩余 n 个，栈内 0 个开始搜索
    cout << dfs(n, 0) << endl;
    return 0;
}

lmz优化版DP代码

#include <iostream>

using namespace std;

long long f[20][20]={0}; // f[i][j] 表示队列剩i个，栈有j个

int main() {
    int n;
    cin >> n;

    // 边界初始化：当队列里没有元素(i=0)时，无论栈里有几个，都只有一种方案(全部弹出)
    for (int j = 0; j <= n; j++) {
        f[0][j] = 1;
    }

    // 开始递推
    // i 代表队列剩余个数，从 1 推到 n
    for (int i = 1; i <= n; i++) {
        // j 代表栈内个数，从 0 推到 n (其实最大也就是 n-i)
        for (int j = 0; j <= n; j++) {
            // 来源1：入栈操作，由 (i-1, j+1) 转移而来
            // 只要 i >= 1 就可以入栈，这里 i 循环本身就是 >=1 的
            // f[i][j] += f[i - 1][j + 1];
            
            // 来源2：出栈操作，由 (i, j-1) 转移而来
            // 前提是栈里得有元素，即 j >= 1
            // if (j >= 1) {
            //     f[i][j] += f[i][j - 1];
            // }
            f[i][j]=(j-1>=0?f[i][j-1]:0)+f[i-1][j+1];//j-1不能小于0,越界f就要当做0
        }
    }

    // 最终答案：初始状态是队列剩 n 个，栈有 0 个
    cout << f[n][0] << endl;

    return 0;
}

luogu题解

https://www.luogu.com.cn/problem/solution/P1044

思路

假设我们用一个函数 $\text{C}(x, y)$ 表示：

• $x$：当前还未入栈的数字个数。
• $y$：当前栈中的数字个数。

我们的目标是计算 $\text{C}(n, 0)$，即从 $n$ 个数字开始，生成输出序列的方式。

在任何状态下，我们有两种选择：

• push 操作：如果还有数字可以入栈（即 $x > 0$），我们可以将一个数字从输入序列移入栈中。这会减少未入栈的数字个数 $x$，同时增加栈中的数字个数 $y$。因此，该操作对应于 $\text{C}(x - 1, y + 1)$。
• pop 操作：如果栈中有数字可以出栈（即 $y > 0$），我们可以将栈顶数字移出到输出序列中。这不会改变未入栈的数字个数 $x$，但会减少栈中的数字个数 $y$。因此，该操作对应于 $\text{C}(x, y - 1)$。

递归的边界条件是：当 $x = 0 \land y = n$ 时，表示所有数字已成功输出为一个序列，这算作一种有效方式，返回 1；其他不合法状态（如 $x < 0 \lor y > n$）返回 0。

递归太慢，所以我们可以用 $DP$，转移方程是：

$$f_{x,y} = f_{x-1, y+1} + f_{x, y-1}$$

#include<bits/stdc++.h>
using namespace std;
int f[20][20],n;
int main(){
	cin>>n;
	for(int x=0;x<=n;x++){
		for(int y=0;y<=n;y++){
			if(!x) f[x][y]=1;
			else if(!y) f[x][y]=f[x-1][y+1];
			else f[x][y]=f[x-1][y+1]+f[x][y-1];
		}
	}
	cout<<f[n][0];
}

​

如果把dp[][]画出来的话这个相当于是从那哪个位置走到哪个位置？

如果我们把这个 DP 数组 f[i][j] 映射到一个二维坐标系里，这道题其实是在计算一个 “从终点倒着走回起点” 的路径计数问题。

为了让你直观理解，我们定义坐标系：

• X 轴（横向）：代表 i（队列里还剩几个数）。
• Y 轴（纵向）：代表 j（栈里有几个数）。

1. 坐标系中的“起点”和“终点”

在这个 DP 代码的逻辑里，计算方向和操作方向是反着的：

• 物理操作的起点（题目开始时）：

  • 队列剩 $n$ 个，栈里 $0$ 个。
  • 坐标：$(n, 0)$。
  • 这是我们最终要求的答案 f[n][0]。

• 物理操作的终点（全部操作做完时）：

  • 队列剩 $0$ 个，栈里也空了（全弹出了）。
  • 坐标：$(0, 0)$。
  • 这是我们的DP 边界条件（f[0][j]=1）。

---

2. 数据的“流动”方向（状态转移图解）

代码逻辑是 f[i][j] += f[i-1][j+1] 和 f[i][j] += f[i][j-1]。这意味着，点 $(i, j)$ 的值，是由它左上方的点和正下方的点汇聚而来的。

我们可以把它想象成水流：水从 $i=0$ 的墙壁流出，最终汇聚到 $(n, 0)$ 这个坑里。

以 $n=3$ 为例，让我们画出 f[i][j] 的网格图：

图例说明：

• 行：代表栈内个数 j (从下往上增长)
• 列：代表队列剩余 i (从左往右增长)
• 箭头：代表数值的贡献来源

j (栈内个数)
^
3 |  1 (边界)
  |  | ↘
2 |  1 -> 2
  |  | ↘  | ↘
1 |  1 -> 2 -> 5
  |  | ↘  | ↘  | ↘
0 |  1 -> 2 -> 5 -> [5] (最终答案)
  -------------------------> i (队列剩余)
     0    1    2     3

详细推导路径：

1. 最左边一列 ($i=0$)：

   • 全是 1。这是初始水源（只要队列空了，剩下的方案只有一种）。

2. 中间的点是如何汇聚的？

   • 看点 $(1, 1)$：它等于左上方的 $(0, 2)$ + 下方的 $(1, 0)$ = $1 + 1 = 2$。
   • 看点 $(2, 1)$：它等于左上方的 $(1, 2)$ + 下方的 $(2, 0)$ = $2 + 3 = 5$。

3. 最终答案 ($i=3, j=0$)：

   • 它等于左上方的 $(2, 1)$ + 下方的 $(3, -1)$（不存在）。
   • 所以它直接继承了 $(2, 1)$ 的值，等于 5。

---

3. 另一种视角的“走迷宫”

如果你想把这个过程想象成一个人在走迷宫，那么这个 DP 实际上是在计算：

从点 $(n, 0)$ 出发，只能做两个动作，走到 $x=0$ 这一条线，一共有多少种走法？

• 动作 1（对应入栈）：往左上方走一步。

  • $i \to i-1$ (队列少1)
  • $j \to j+1$ (栈多1)
  • 限制：到了最左边就到了终点。

• 动作 2（对应出栈）：往正下方走一步。

  • $i$ 不变
  • $j \to j-1$ (栈少1)
  • 限制：不能钻到地底下（$j$ 不能小于 0）。

总结图示：

目标：从 (n, 0) 走到 (0, ?)

(i-1, j+1)  <-- (入栈/Push) -- (i, j)
   ^                               |
   |                               | (出栈/Pop)
 (终点线)                          v
                               (i, j-1)

所以，这个 DP 数组画出来，就是一张从右下角 $(n, 0)$ 向左边 $i=0$ 墙壁反向渗透的路径图。

为什么我看下面代码觉得f[i][j] += f[i][j - 1];是代表入栈？这里j-1变成j不是说明入栈吗？还是我哪里理解错了？

// 来源2：出栈操作，由 (i, j-1) 转移而来
        // 前提是栈里得有元素，即 j >= 1
        if (j >= 1) {
            f[i][j] += f[i][j - 1];
        }

你的直觉非常敏锐！单看 f[i][j-1] 到 f[i][j] 的下标变化（$j-1 \to j$），确实很像是在堆栈中“增加”了一个元素（入栈）。

但这里之所以注释说是“出栈”，是因为这个 DP（动态规划）的状态定义和推导方向是 “倒着看” 或者说是 “基于后续步骤” 的。

让我来为你拆解一下这里的逻辑陷阱。

1. 核心分歧：是“从哪来”，还是“到哪去”？

你的理解（通常的“到达型” DP）：

你潜意识里认为 f[i][j] 代表的是 “经过一系列操作后，到达状态 $(i, j)$ 的方案数”。 如果是这样，你是对的：要从栈里只有 $j-1$ 个元素变成有 $j$ 个元素，必须进行 入栈 操作。

代码的实际逻辑（“剩余型” DP / 递归改写）：

这个代码的思路其实是把递归（DFS）的过程直接改写成了数组形式。 这里的 f[i][j] 意思其实是：“当前队列剩 $i$ 个，栈里有 $j$ 个，后续还能走出多少种合法的全过程？”

让我们站在当前状态 $(i, j)$ 往未来看：

1. 当前状态：队列剩 $i$ 个，栈里有 $j$ 个。
2. 执行操作：出栈 (Pop)。
3. 变成状态：队列还是 $i$ 个，栈里变少了一个，变成了 $j-1$ 个。即状态 $(i, j-1)$。
4. 结论：既然我可以从当前状态通过“出栈”走到 $(i, j-1)$，那么状态 $(i, j-1)$ 后续能产生的所有方案，都属于当前状态 $(i, j)$ 的一部分。

所以代码写的是：

f[i][j] += f[i][j - 1]; // 把“出栈后那个状态”的方案数加到“当前状态”来

2. 图解对比

为了更清楚，我们模拟一下：

场景： 栈里有 $j$ 个元素。

• 动作：我们决定执行一次 Pop (出栈)。
• 结果：栈里剩下了 $j-1$ 个元素。

在代码逻辑中：

$$\text{当前状态}(i, j) \xrightarrow{\text{出栈动作}} \text{子状态}(i, j-1) $$

因为我们要求的是总方案数，所以：

$$\text{方案数}(i, j) = \text{方案数}(\text{入栈后的状态}) + \text{方案数}(\text{出栈后的状态}) $$$$f[i][j] = f[i-1][j+1] + f[i][j-1]$$

3. 为什么你会觉得是入栈？

你的理解是基于数组下标的视角：

• 你在看代码 f[i][j] += f[i][j-1] 时，感觉像是“用 $j-1$ 的值去更新 $j$ 的值”。
• 在你的视角里：$j-1 \to j$ 是变多了，所以像入栈。

但实际上，这里的加法并不是“物理上的入栈”，而是**“方案数的汇总”。 它的含义是：“如果我现在出栈，我就变成了状态 $j-1$，所以我继承了状态 $j-1$ 的所有可能性。”**

总结

• 你的直觉：从 $j-1$ 变成 $j$ 是入栈。（这是对的，物理过程确实如此）。
• 代码逻辑：我现在是 $j$，我下一步可以选择出栈变成 $j-1$。所以我把 $j-1$ 那种情况的方案数拿过来加在自己头上。（这是“回溯/递归”的思维）。

所以，代码里的 f[i][j-1] 确实对应的是出栈操作后的结果。

这道题（P1044 [NOIP 2003 普及组] 栈）是算法竞赛中关于 卡特兰数（Catalan Number） 的经典入门题。

以下分别给出三种不同思路的 C++ 解答代码：递归/记忆化搜索、动态规划 (DP) 和 数学公式 (卡特兰数)。

---

思路一：记忆化搜索（DFS + 剪枝）

这是最符合题目操作直觉的思路。我们定义状态 (x, y)，其中 x 代表队列中还没有进栈的元素个数，y 代表栈中当前已经存在的元素个数。

对于任何状态，只要满足条件，就有两种选择：

1. 进栈：如果队列里还有数 (x > 0)，可以把一个数放进栈里。状态变为 (x-1, y+1)。
2. 出栈：如果栈里有数 (y > 0)，可以弹出一个数。状态变为 (x, y-1)。

如果不加记忆化数组 mem，时间复杂度是指数级的；加上后，每个状态只会被计算一次。

#include <iostream>
#include <algorithm>

using namespace std;

// mem[i][j] 用来记录当队列剩余 i 个，栈内有 j 个时的方案数
// 使用 long long 防止运算过程中溢出（虽然 n=18 时 int 其实够用）
long long mem[20][20]; 
int n;

// x: 队列中剩余待入栈的个数
// y: 栈中当前的个数
long long dfs(int x, int y) {
    // 递归边界：如果队列里没数了 (x==0)，剩下的步骤只有一种：
    // 就是把栈里的 y 个数依次弹出来。所以返回 1。
    if (x == 0) return 1;
    
    // 如果这个状态之前算过了，直接返回，避免重复计算
    if (mem[x][y] != 0) return mem[x][y];
    
    long long count = 0;
    
    // 选择1: 进栈 (前提是队列里还有数)
    if (x > 0) {
        count += dfs(x - 1, y + 1);
    }
    
    // 选择2: 出栈 (前提是栈里有数)
    if (y > 0) {
        count += dfs(x, y - 1);
    }
    
    // 记录结果并返回
    return mem[x][y] = count;
}

int main() {
    cin >> n;
    // 从队列剩余 n 个，栈内 0 个开始搜索
    cout << dfs(n, 0) << endl;
    return 0;
}

---

思路二：动态规划 (DP)

将思路一的递归过程转化为迭代推导。我们定义二维数组 f[i][j]。

• 状态定义：f[i][j] 表示 队列里还剩 i 个数，栈里有 j 个数 时，能够产生的合法输出序列总数。
• 状态转移方程：$$f[i][j] = f[i-1][j+1] + f[i][j-1]$$
  • f[i-1][j+1] 代表进行了一次入栈操作带来的方案数（如果有剩余元素可入）。
  • f[i][j-1] 代表进行了一次出栈操作带来的方案数（如果栈不为空）。
• 边界条件：f[0][j] = 1（队列无元素，只能一直出栈，方案数为1）。

#include <iostream>

using namespace std;

long long f[20][20]; // f[i][j] 表示队列剩i个，栈有j个

int main() {
    int n;
    cin >> n;

    // 边界初始化：当队列里没有元素(i=0)时，无论栈里有几个，都只有一种方案(全部弹出)
    for (int j = 0; j <= n; j++) {
        f[0][j] = 1;
    }

    // 开始递推
    // i 代表队列剩余个数，从 1 推到 n
    for (int i = 1; i <= n; i++) {
        // j 代表栈内个数，从 0 推到 n (其实最大也就是 n-i)
        for (int j = 0; j <= n; j++) {
            // 来源1：入栈操作，由 (i-1, j+1) 转移而来
            // 只要 i >= 1 就可以入栈，这里 i 循环本身就是 >=1 的
            f[i][j] += f[i - 1][j + 1];
            
            // 来源2：出栈操作，由 (i, j-1) 转移而来
            // 前提是栈里得有元素，即 j >= 1
            if (j >= 1) {
                f[i][j] += f[i][j - 1];
            }
        }
    }

    // 最终答案：初始状态是队列剩 n 个，栈有 0 个
    cout << f[n][0] << endl;

    return 0;
}

---

思路三：数学公式（卡特兰数）

这道题的本质是求卡特兰数（Catalan Number）。 一个进栈顺序为 $1, 2, \dots, n$ 的序列，其合法的出栈序列总数为第 $n$ 项卡特兰数。

卡特兰数通项公式：

$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!(n+1)!} $$

或者使用递推公式（更适合编程计算，避免大数阶乘溢出）：

$$C_n = C_{n-1} \times \frac{4n - 2}{n + 1}$$

这里我们使用递推公式来实现，计算复杂度为 $O(n)$。

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    // C_n 代表第 n 项卡特兰数
    // C_0 = 1, C_1 = 1
    long long ans = 1; 

    // 使用递推公式 C_n = C_{n-1} * (4*n - 2) / (n + 1)
    // 注意：编程时要把 i 当作当前的 n
    for (int i = 1; i <= n; i++) {
        // 先乘后除，防止整数除法精度丢失
        // 必须使用 long long，因为分子 (4*i - 2) * ans 可能会超过 int 范围
        ans = ans * (4 * i - 2) / (i + 1);
    }

    cout << ans << endl;

    return 0;
}

总结

• 思路一（DFS）：最容易理解，适合初学者建立对“状态”的认知，必须加记忆化。
• 思路二（DP）：是思路一的非递归版，逻辑严密，不易爆栈。
• 思路三（数学）：代码最短，效率最高，但需要知道卡特兰数的数学背景。在比赛中，如果看出了是卡特兰数模型，直接套公式是最快的。

这道题（NOIP 2003 普及组 T3）是数据结构与算法中的一道殿堂级经典题目。它不仅考查了对“栈”这个数据结构运作原理的理解，更是一道非常标准的动态规划（DP）或者数学组合题目。

如果不直接告诉你那个著名的数学公式，我们可以通过模拟栈的操作过程来推导出答案。这里给你提供三个层进的思路。

思路一：模拟操作过程（递归 / DFS）

我们要计算总方案数，其实就是问：有多少种合法的“进栈”和“出栈”的操作序列？

想象一下，在这个过程中，我们只关心两件事（状态）：

1. 队列里还剩几个数没进栈？（记为 i）
2. 栈里现在有几个数？（记为 j）

每一次操作，我们只有两种选择：

1. 进栈（Push）：

   • 前提条件：队列里还有数（i > 0）。
   • 操作后果：队列少 1 个，栈里多 1 个。
   • 状态变化：(i, j) $\to$ (i-1, j+1)

2. 出栈（Pop）：

   • 前提条件：栈里有数（j > 0）。
   • 操作后果：栈里少 1 个（队列不变）。
   • 状态变化：(i, j) $\to$ (i, j-1)

递归边界：

• 当队列里没数了（i == 0），剩下的栈里的数只能一口气全弹出来，这一种情况算作 1 种有效方案，直接返回 1。

提示代码逻辑：

long long dfs(int i, int j) {
    if (i == 0) return 1; // 没数可进了，只能全出，只有一种路
    
    long long count = 0;
    // 选择1：进栈
    if (i > 0) count += dfs(i - 1, j + 1);
    
    // 选择2：出栈
    if (j > 0) count += dfs(i, j - 1);
    
    return count;
}

注意：直接这样写递归在 $n=18$ 时可能会因为重复计算而超时，你需要加上记忆化数组 mem[20][20] 来保存算过的状态。

---

思路二：动态规划 (DP)

如果你理解了上面的记忆化搜索，其实这就已经是动态规划了。我们可以把递归改成递推（填表格）。

定义状态： f[i][j] 表示：当队列里还剩 i 个数，且栈里有 j 个数时，后续能产生的合法方案数。

状态转移方程： 根据上面的两种选择，f[i][j] 的方案数等于“选择进栈后的方案数”加上“选择出栈后的方案数”（每个状态上只有两种转移选择）。

$$f[i][j] = f[i-1][j+1] + f[i][j-1]$$

(当然要判断边界，比如 j=0 时不能出栈，只能由进栈转移而来)

初始状态： 当 i=0 时，无论 j 是多少，都只有一种方案（全部弹出），即 f[0][j] = 1。

目标答案： 最开始队列有 n 个数，栈里有 0 个数，所以答案是 f[n][0]。

---

思路三：数学规律（卡特兰数）

如果你列出 $n=1, 2, 3, 4$ 的答案：

• $n=1$: 1
• $n=2$: 2
• $n=3$: 5
• $n=4$: 14
• $n=5$: 42

这其实是著名的卡特兰数 (Catalan Number) 数列。 这个数列在很多这类“不跨越边界”、“括号匹配”、“二叉树形态计数”的问题中都会出现。

通项公式：

$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$

递推公式（更适合编程）：

$$h(n) = \sum_{k=0}^{n-1} h(k) \times h(n-1-k)$$

即：$h(n) = h(0)h(n-1) + h(1)h(n-2) + \dots + h(n-1)h(0)$

为什么是这个公式？（选读理解） 假设最后一个出栈的元素是 $k$（因为输入是 $1 \dots n$，最后出栈的 $k$ 把序列分成了两半）：

• 比 $k$ 小的数（$1 \dots k-1$）肯定在 $k$ 之前入栈并出栈了（共有 $k-1$ 个数）。这部分的方案数是 $h(k-1)$。
• 比 $k$ 大的数（$k+1 \dots n$）肯定在 $k$ 之后入栈并出栈（共有 $n-k$ 个数）。这部分的方案数是 $h(n-k)$。
• 乘法原理：当前情况就是 $h(k-1) \times h(n-k)$。
• 枚举 $k$ 的所有可能位置，加起来就是总数。

---

总结建议

1. 数据范围：$n \le 18$。虽然结果 4亿多在 int 范围内，但为了养成好习惯，建议使用 long long。
2. 推荐方法：作为练习，思路一（加记忆化） 或者 思路二（DP） 是最好的，因为它们不需要背数学公式，更能锻炼你的逻辑思维。如果想装酷，可以用思路三。

快去试着实现一下吧！

老版本题解，不推荐

C :

# include <stdio.h>
# include <string.h>
int main()
{
	long long int ans = 1;
	int i, n;
	scanf("%d", &n);
	if(n > 1)
	{
		for(i = 2; i <= n; ++i)
			ans = ans * (4 * i - 2) / (i + 1);
	}
	printf("%lld", ans);

	return 0;
}

C++ :

#include<iostream>
#include<cstdio>
using namespace std;
double solve(int n)
{
  double a=1,b=1;
  for(int i=2*n;i>n+1;i--)
    a*=i;
  for(int j=1;j<=n;j++)
    b*=j;
return a/b;
}
int main()
{
  int n;
  while(cin>>n)
  {
    printf("%.lf\n",solve(n));
  }
  return 0;
}

Pascal :

program stack1(input,output);
const max=18;
var f:array[0..max] of longint;
    i,j,n:integer;
begin
   readln(n);
   f[0]:=1;
   for i:=1 to n do
      begin
        f[i]:=0;
        for j:=0 to i-1 do f[i]:=f[i]+f[j]*f[i-j-1]
     end;
   writeln(f[n]);
end.

Java :

import java.util.Scanner;
public class Main {
	static int f(int n,int m){
		if(0==n) return 1;
		if(0==m) return f(n-1,m+1);
		return f(n,m-1)+f(n-1,m+1);
	}
	static int f(int n){
		return f(n,0);
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		if(1<=n&&n<=15){
			System.out.println(f(n));
		}else if(16==n){
			System.out.println(35357670);
		}else if(17==n){
			System.out.println(129644790);
		}else if(18==n){
			System.out.println(477638700);
		}
	}
}