蓝桥杯算法题：栈（Stack）

这道题考的是递推动态规划，可能不是很难，不过这是自己第一次靠自己想出状态转移方程，所以纪念一下：

要做这些题目，首先要把题目中会出现什么状态给找出来，然后想想他们的状态可以通过什么操作转移，进而写出状态转移方程

这道题的状态可以分为三个，一个是已输出序列，另一个是栈中序列，另一个是未输入序列，那有什么操作可以改变序列呢，有两个，操作一是未输入序列往栈中放数字，操作二是栈中序列把数字输出到已输出序列。这时设置一数组f[i][j][k]，i表示已输出序列长度，j表示栈中序列长度，k表示未输入序列的长度，则可以根据红字的操作写出状态转移方程：f[i][j][k]=f[i][j-1][k+1]+f[i-1][j+1][k];

其中[i][j-1][k+1]变为f[i][j][k]表示操作一，f[i-1][j+1][k]变成f[i][j][k]表示操作二（注意有些状态只能由一个操作转换而来，不然就发生不可能的情况，即越界）比如说{2,0,1}只能由状态{1,1,1}转变而来，不能由{2,-1,2}转变而来

#include<bits/stdc++.h>
using namespace std;
int f[20][20][20];
int main(){int n;cin>>n;for(int i=0;i<=n;i++){f[0][i][n-i]=1;f[i][0][n-i]=1;//这两种情况，栈里数的顺序是唯一的，所以个数也就为1}for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){if(i+j+k==n){if(j==n&&k<=n-1)f[i][j][k]=f[i][j-1][k+1];else if(j==0||k==n)f[i][j][k]=f[i-1][j+1][k];else f[i][j][k]=f[i-1][j+1][k]+f[i][j-1][k+1];}}}} cout<<f[n][0][0]<<endl;
}

不过我又去看了别人的题解，似乎更好，又学到了，其实我也想过用一个数的位置来看状态，不过没能想得那么利索