题目：
输入格式
输入文件只含一个整数n（1≤n≤18）。

输出格式
输出文件只有一行，即可能输出序列的总数目(类似栈先进先出)。

错误思路：从序列中找规律
n = 1 ,1进1出一种序列
n = 2, 1进1出，2进2出和 1进2进，2出1出，两种序列
n = 3，123->123 213 231 132 321
n = 4, 1234->4321,

正确思路：
题目本质：栈内个数和栈外个数的动态变化每种变化都有一个固定的值
例如：栈内有一个数，栈外有一个数的情况：
要么栈内的数出去->栈内0个数，栈外一个数
要么栈外的数入栈->栈内2个数，栈外一个数
和栈内栈外的数是几没有关系

dp思路：
设dp[i][j] i表示栈内元素个数，j表示栈外元素个数
最优子结构：[i-1][j] [i+1][j-1]
边界：栈外没有元素时，无论栈内几个元素，出栈顺序都为一种，即j = 0, dp[i][0] = 1
状态转化方程：dp[i][j] = dp[i-1][j] + dp[i+1][j-1]

代码：
法一：动态规划 dp 记忆搜索

include

using namespace std;

long long dp[25][25];//存储不同情况的状态（出栈序列数量）

int main(){
int n;
cin>>n;
//边界栈外没有元素的情况
for(int i = 0; i <= n; i++){ //存在栈内外没有元素的情况，n个数有n+1种情况
dp[i][0] = 1;
}
for(int j = 1; j <= n; j++){ //从栈外有一个元素开始讨论
for(int i = 0; i <= n; i++){
if(i == 0){ //栈内没有元素，只能入栈
dp[i][j] = dp[i+1][j-1];
}
else{
dp[i][j] = dp[i+1][j-1] + dp[i-1][j];
}
}
}
cout<<dp[0][n];
}

法二 dfs 递归
代码：

include

using namespace std;

long long dp[25][25];
int n;

long long dfs(int k,int n){//栈内0 栈外n
if(dp[k][n]){
return dp[k][n];
}
if(n == 0){//栈外没有元素
return 1;
}
if(k == 0){//栈内没有元素
return dfs(k+1,n-1);
}
return dfs(k+1,n-1) + dfs(k-1,n);

}

int main(){
cin>>n;
cout<<dfs(0,n);//栈内0 栈外n
}