线上OJ 地址:
一本通:1924:【03NOIP普及组】栈 (opens in a new tab)
AcWing:415. 栈 (opens in a new tab)
洛谷:P1044 [NOIP2003 普及组] 栈 (opens in a new tab)
核心思想
1、这类题目和火车进站出站是同一类问题,常规解法有两种。一、动态规划;二、卡特兰公式
解法一:动态规划
1、设 f[i][j]: i表示进栈的个数,j表示“进栈的i个”中出栈的个数。所以 j≤i
举例:
f[1][0]=1:进栈1个元素,出栈0个元素。此时只有1种可能,就是进栈的唯一元素不动。
f[1][1]=1:进栈1个元素,出栈1个元素。此时只有1种可能,就是把进栈的唯一元素直接出栈。
f[2][0]=1:进栈2个元素,出栈0个元素。此时只有1种可能,就是进栈的两个元素都不动。
f[2][1]:进栈2个元素,出栈1个元素。此时有2种可能,第一种是在f[1][1]的情况下第2个元素进栈;第二种可能是在f[2][0]的情况下出栈一个元素
......
2、根据以上推导,可以得到动态转移方程: 即 “进栈 i 个,出栈 j 个” 由 两种 状态转移而来:
① 进栈 i-1 个,出栈 j 个(此时再进栈1个就好);
② 进栈 i 个,出栈 j-1 个(此时再出栈1个就好)
3、初始化:不管进栈几个,出栈为0的,都只有1种可能性,就是都不出
4、注意 j≤i
5、最后要输出的结果就是 f[n][n],表示进栈n个,出栈n个的可能性
6、注:动态规划的好处是可以求出任意进栈出栈 f[i][j] 的数量。
题解代码:
解法一、动态规划
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 20;
ll f[N][N];
// f[i][j]: i表示进栈的个数,j表示“进栈的i个”中出栈的个数。所以j<=i
// f[i][j] = f[i-1][j] + f[i][j-1]
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i <= n; i++) f[i][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
f[i][j] = f[i-1][j] + f[i][j-1];
printf("%d", f[n][n]);
return 0;
}