【题目来源】
洛谷：P1044 [NOIP 2003 普及组] 栈 - 洛谷 (luogu.com.cn)
【题目描述】
宁宁考虑的是这样一个问题：一个操作数序列，\(1,2,\dots,n\)（图示为 \(1\) 到 \(3\) 的情况），栈 \(A\) 的深度大于 \(n\)。
现在可以进行两种操作，
- 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
- 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）
使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。
（原始状态如上图所示）
你的程序将对给定的 \(n\)，计算并输出由操作数序列 \(1,2,\dots,n\) 经过操作可能得到的输出序列的总数。
【输入】
输入文件只含一个整数 \(n(1\le n\le 18)\)。
【输出】
输出文件只有一行，即可能输出序列的总数目。
【输入样例】
3
【输出样例】
5
【解题思路】
【算法标签】
《洛谷 P1044 栈》 #动态规划,dp# #数学# #递推# #Catalan数# #栈# #NOIP普及组# #2003#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int main() {long long n; // 输入的数字nlong long f[20] = {1, 1, 2}; // 初始化前三个卡特兰数cin >> n; // 读取输入n// 计算卡特兰数f[3]到f[n]for (int i = 3; i <= n; i++) {f[i] = 0; // 初始化当前卡特兰数为0// 根据卡特兰数递推公式计算for (int k = 1; k <= i; k++) {f[i] += f[k - 1] * f[i - k]; // 累加各项乘积}}cout << f[n]; // 输出第n个卡特兰数return 0;
}
// 使用记忆化DFS重写一遍
#include <bits/stdc++.h>
using namespace std;int n;
int dp[20][20][20]; // 记忆化数组// 记忆化DFS函数
// x: 当前已确定的左括号数量
// y: 可用的右括号数量（已匹配的左括号）
// z: 剩余未使用的左括号数量
// n: 总括号对数
int dfs(int x, int y, int z, int n) {// 所有括号都已使用if (x == n) return 1;// 如果已经计算过，直接返回结果if (dp[x][y][z]) return dp[x][y][z];// 尝试添加右括号（如果有可匹配的左括号）if (y > 0) dp[x][y][z] += dfs(x + 1, y - 1, z, n);// 尝试添加左括号（如果还有剩余）if (z > 0) dp[x][y][z] += dfs(x, y + 1, z - 1, n);return dp[x][y][z];
}int main() {cin >> n;// 初始状态：0个已确定的左括号，0个可匹配的右括号，n个剩余的左括号cout << dfs(0, 0, n, n);return 0;
}
【运行结果】
3
5