31 lines
1.0 KiB
C++
31 lines
1.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 20;
|
||
typedef long long LL;
|
||
|
||
int n;
|
||
// 定义一个二维数组f[i,j]f[i,j]，用下标 i 表示队列里还有几个待排的数，
|
||
// j 表示栈里有 j 个数，f[i,j]表示此时的情况数
|
||
// 不重不漏的描述了所有情况
|
||
LL f[N][N]; //记忆化搜索
|
||
|
||
LL dfs(int i, int j) {
|
||
//算过
|
||
if (f[i][j]) return f[i][j];
|
||
//(1)队列空，栈空
|
||
if (i == 0 && j == 0) f[i][j] += 1; //这是递归出口，增加一种方法
|
||
//(2)队列空,栈不空
|
||
if (i == 0 && j > 0) f[i][j] += 1;//只能一个个蹦出去啦~
|
||
//(3)队列不空,栈空
|
||
if (i > 0 && j == 0) f[i][j] += dfs(i - 1, j + 1);//从队列中取一个，放入到栈中
|
||
//(4)队列不空,栈不空
|
||
if (i > 0 && j > 0) f[i][j] += dfs(i, j - 1) + dfs(i - 1, j + 1);//有两种选择，一是队列不动，栈中出去一个；另一种是队列取一个，放入栈中
|
||
return f[i][j];
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
printf("%lld", dfs(n, 0));
|
||
return 0;
|
||
} |