进出栈序列问题

洛谷-P1044-栈

分析

见《进阶指南》第51页。

实现

// 方法二
#include <iostream>
using namespace std;

int f[20];

int main () {
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; ++ i)
        for (int k = 1; k <= i; ++ k)
            f[i] += f[k - 1] * f[i - k];
    cout << f[n] << endl;
    return 0;
}
// 方法三
#include <iostream>
#include <cstring>
using namespace std;

int f[20][20];

int dfs (int i, int j) {
    if (f[i][j] != -1) return f[i][j];

    int res = 0;
    if (i - 1 >= 0)
        res += dfs(i - 1, j + 1); // 入栈
    if (j - 1 >= 0)
        res += dfs(i, j - 1); // 出栈
    return f[i][j] = res;
}

int main () {
    int n;
    cin >> n;
    memset(f, -1, sizeof(f));
    f[0][0] = 1;
    cout << dfs(n, 0) << endl;
    return 0;
}