洛谷题单指南-递推与递归-P1044 [NOIP2003 普及组] 栈

原题链接：https://www.luogu.com.cn/problem/P1044

题意解读：一组数入栈、出栈的方案数，如果了解卡特兰数，此题可以秒杀；如果不了解，也可以通过递归或者递推来解决 ；最次，可以通过DFS暴搜出方案数，当然对于n个数，一共有n次入栈、n次出栈，一共2n次，每次要么入栈要么出栈，总搜索次数在2²ⁿ规模，n最大18，会超时，实测只能得到60分。

解题思路：

1、DFS暴搜法（60分）

对于序列中的每一个数k，有两种操作：入栈、出栈

入栈后，下一次针对数k+1继续进行DFS

出栈的前提是栈不为空

注意DFS前后需要保存栈和恢复栈，以便于回溯。

60分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

stack<int> stk;
int ans;
int n;

void dfs(int k) 
{
    if(k > n)
    {
        while(stk.size()) stk.pop();
        ans++;
        return;
    }

    //压栈
    stack<int> stk1(stk);
    stk.push(k);
    dfs(k + 1); //压栈，序列中下一次变成k+1
    stk = stk1;

    //弹栈
    if(stk.size())
    {
        stack<int> stk2(stk);
        stk.pop();
        dfs(k); //弹栈，序列中下一次还是k
        stk = stk2;
    }
}

int main()
{
    cin >> n;
    dfs(1); //从序列中1开始
    cout << ans;

    return 0;
}

2、递归（动态规划）

设dp(i, j)表示对序列中i个数，堆栈中j个数操作可得到的输出方案总数。

当堆栈为空时（j==0），只能做入栈操作，因此dp(i, j) = dp(i - 1, j + 1)。说明：入栈操作i-1，j+1

当堆栈不为空时（j!=0）,既能做入栈操作，又能做出栈操作，因此dp(i, j) = dp(i - 1, j + 1) + dp(i, j - 1)。说明：出栈操作i不变，j-1

初始条件：

当序列中时0个数，无论堆栈中有多少个数，输出方案都是1，dp(0, j) = 1。说明：只需要将所有堆栈元素出栈，即一种输出方案。

通过递归实现以上步骤：

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

int f[N][N];
int n;

//i是序列中的个数，j是堆栈中的个数，要求的就是i=n，j=0的结果
int dp(int i, int j)
{
    if(f[i][j]) return f[i][j]; //如果已经计算过了，不要重复计算
    if(i == 0) return 1; //只要序列中没有数了，就是一次性把堆栈弹出一种方案
    if(j == 0) //栈为空的时候，只能压栈，i减少，j增加
    {
        f[i][j] += dp(i - 1,j + 1);
    }
    else //栈不为空，既可以压栈，又可以弹栈
    {
        f[i][j] += dp(i - 1, j + 1) + dp(i, j - 1); 
    }

    return f[i][j];
}

int main()
{
    cin >> n;
    cout << dp(n, 0); //计算n个序列，栈为空的方案数
    return 0;
}

3、递推（推荐）

设f[n]为n个数入栈出栈后输出的方案数

设1是第k个输出，k可能为1~n

在1之前有k - 1个数，方案数为f[k - 1]

在1之后有n - k个数，方案数为f[n - k]

根据乘法原理，当1是第k个输出时，方案数为f[k - 1] * f[n - k]

又k可以取1~n，根据加法原理，总方案数为f[n] = f[0] * f[n-1] + f[1] * f[n-2] + ... + f[n-1] * f[0] 

举例：

初始值：f[0] = 1，f[1] = 1

f[2] = f[0]*f[1] + f[1]*f[0] = 2

f[3] = f[0]*f[2] + f[1]*f[1] + f[2]*f[0] = 5

f[4] = f[0]*[3] + f[1] *f[2] + f[2]*f[1] + f[3]*f[0] = 14

...

通过递推实现以上步骤：

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

int f[N];
int n;

int main()
{
    cin >> n;
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int k = 1; k <= i; k++)
        {
            f[i] += f[k - 1] * f[i - k];
        }
    }
    cout << f[n];

    return 0;
}

4、卡特兰数

方案3就是卡特兰数的递推原理。

更进一步，此题是n次入栈、n次出栈的排列组合，且在任意时候出栈数都不能超过入栈数，是典型的卡特兰数，这里不加证明

卡特兰数的公式为C(2n,n) - C(2n, n-1) = C(2n, n) / (n + 1)

通过递推实现组合计算，加long long防止溢出

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 40;

long long c[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i <= 36; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(!j) c[i][j] = 1;
            else c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }
    cout << c[2 * n][n] / (n + 1);

    return 0;
}