题解：P1044 [NOIP 2003 普及组] 栈

· · 题解

看题解里好多巨佬呢，都是卡特兰数，本蒟蒻来发一篇递推的吧。

我的思想主要是将他从最终序列倒退回去。

SOLUTION

我们首先定义 DP 状态 dp_{i,j}，表示当前还有 i 个元素没有入栈，栈中有 j 个元素时的情况可能数。

我们首先给出一个初始化，如果此时没有元素需要入栈，那么只有一种情况，这是很容易理解的。

接下来就是转移方程了，我们分为两种情况讨论。

第一种是栈内还有元素，那我们可以选择出栈和入栈，将这两种情况的方案数相加即可。

第二种是没有元素了，只能选择入栈。

看到这的小伙伴应该已经有了想法，但如果还没有懂，那么就请看下面的代码。

CODE

#include<bits/stdc++.h>
using namespace std;
int dp[25][25] , n;
int main(){
    cin >> n;
    for(int i = 0;i <= n;i++)dp[0][i] = 1;//初始化
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= n;j++){
            if(j)dp[i][j] = dp[i][j - 1] + dp[i - 1][j + 1];//栈中有元素
            else dp[i][j] = dp[i - 1][j + 1];//栈中无元素
        }
    }
    cout << dp[n][0];
    return 0;
}