洛谷 P1044 栈

// 洛谷 P1044 栈 —— 第 ① 版：把每一步「进栈还是出栈」都搜一遍（对，但太慢）
//
// 输入：n（1 <= n <= 18）
// 输出：可能的输出序列总数
//
// 这份为什么存在：这道题第一眼看不出公式，但**过程是清清楚楚的** ——
// 每一步只有两种动作，那就把两种都试一遍。这正是第 1 章讲的「信任函数」：
//
//   f(rest, in) = 「还有 rest 个数没进栈、栈里现在有 in 个，往后能凑出多少种输出序列」
//
//   · rest == 0：剩下的只能一个一个弹出来，顺序是定死的 ⇒ 1 种
//   · 否则可以「进一个」：f(rest-1, in+1)
//   · 栈非空还可以「弹一个」：f(rest, in-1)
//
// ⚠ 它是对的，但**同一个 (rest, in) 会被不同的路径反复问到**。
//    n = 16 时要走 84 118 036 个节点，n = 18 已经到十亿量级 —— 一秒钟的时限扛不住。
//    ⇒ 病根和 P1255 一模一样：**子问题重叠**。下一版加个数组就好。

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

int n;

long long f(int rest, int in) {
    if (rest == 0) return 1;                           // 剩下的只能依次弹出，只有一种
    long long total = f(rest - 1, in + 1);             // 进栈
    if (in > 0) total += f(rest, in - 1);              // 出栈
    return total;
}

int main() {
    if (!(cin >> n)) return 0;
    cout << f(n, 0) << "\n";
    return 0;
}

// 洛谷 P1044 栈 —— 第 ② 版：同一个递归，加一张二维表（★ 这一版就能 AC）
//
// 输入：n
// 输出：可能的输出序列总数（和第 ① 版完全一样）
//
// 这份为什么存在：第 ① 版慢在「同一个 (rest, in) 被问了很多遍」。
// **状态只有 (rest, in) 两个量，各自不超过 n** ⇒ 一共才 19 × 19 = 361 个格子，
// 每个只需要算一次。
//
// ★ 这就是记忆化的判断标准，值得背下来：
//   **先看清楚「一个子问题由哪几个量唯一决定」，再看这几个量的组合有多少种。**
//   组合数不大（这里 361），记忆化就一定划算。
//
// 数字：n = 18 时第 ① 版要走十亿量级的节点，这一版只算 361 个格子。
//
// ⚠ memo 初值用 -1，不能用 0 —— 0 是**合法的答案**吗？这道题不是（答案恒 >= 1），
//   但养成用 -1 的习惯更安全：换一道题，0 很可能就是个真答案了。

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

int n;
long long memo[25][25];

long long f(int rest, int in) {
    if (rest == 0) return 1;
    if (memo[rest][in] >= 0) return memo[rest][in];     // ★ 算过了
    long long total = f(rest - 1, in + 1);
    if (in > 0) total += f(rest, in - 1);
    return memo[rest][in] = total;                      // ★ 存下来
}

int main() {
    if (!(cin >> n)) return 0;
    memset(memo, -1, sizeof memo);
    cout << f(n, 0) << "\n";
    return 0;
}

// 洛谷 P1044 栈 —— 第 ③ 版：换个角度想，它是卡特兰数
//
// 输入：n
// 输出：可能的输出序列总数
//
// 这份为什么存在：记忆化已经能过了。这一版不是为了更快（都是一瞬间），
// 是为了**看清这道题到底是什么**。
//
// 换个角度：盯住「**1 号数字是第几个被输出的**」。
// 假设 1 是第 k+1 个被输出的，那么在它之前必须先输出 k 个数 ——
// 而这 k 个数只能来自 2..k+1（因为 1 还压在栈底，比它晚进栈的才可能先出来）。
// 于是整个问题被切成两段互不干扰的小问题：
//
//   前面那段：k 个数自己排  ⇒ f(k)
//   后面那段：剩下 n-1-k 个数自己排 ⇒ f(n-1-k)
//
//   f(n) = f(0)·f(n-1) + f(1)·f(n-2) + ... + f(n-1)·f(0)      f(0) = 1
//
// 这就是**卡特兰数**（Catalan）。f(3) = 5，正好是样例。
//
// ★ 值得记住的不是「卡特兰数」这个名字，是那个动作：
//   **盯住某一个元素，按它的位置把问题劈成两半。** 第 26 章区间 DP 用的是同一招。
//
// ⚠ 但也别倒过来想：**先会写第 ② 版的记忆化，再去认公式。**
//   认不出公式的题多得是，而「状态 + 记忆化」永远能用。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<long long> f(n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int k = 0; k < i; k++) f[i] += f[k] * f[i - 1 - k];

    cout << f[n] << "\n";
    return 0;
}

// P1044 的两个递归版本各走多少个节点 —— 换一把可复现的尺子
//
// 输入：无（表是写死的几个 n；第 ① 列超过 n = 16 就跑不动了，所以表到 16 为止）
// 输出：一张表，对每个 n 列出
//         答案 f(n)        可能的输出序列总数
//         1.没有记忆化      走过的节点数
//         2.有记忆化        调用次数（含直接命中缓存的那些）
//         真正算过的格子     记忆化下有多少个 (rest, in) 被真的算了一遍
//
// ★ 最后一列是这道题的题眼：**它正好是 n(n+1)/2**，因为能走到的状态就是
//   rest 取 1..n、in 取 0..n-rest —— 数一数就这么多，和答案有多大毫无关系。
//   ⇒ 「该不该上记忆化」这个判断，看的就是它：状态的组合数够小，就一定划算。
//
// ⚠ 第 ① 列的增长和答案本身一个量级（都是卡特兰数那条曲线），
//   所以它和 P1255、P1028 是同一种慢：**工作量跟着答案一起爆炸**。

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

int n;
long long naiveNodes = 0;

long long naive(int rest, int in) {
    naiveNodes++;
    if (rest == 0) return 1;
    long long total = naive(rest - 1, in + 1);
    if (in > 0) total += naive(rest, in - 1);
    return total;
}

long long memo[25][25];
long long memoCalls = 0, memoFilled = 0;

long long withMemo(int rest, int in) {
    memoCalls++;
    if (rest == 0) return 1;
    if (memo[rest][in] >= 0) return memo[rest][in];
    memoFilled++;
    long long total = withMemo(rest - 1, in + 1);
    if (in > 0) total += withMemo(rest, in - 1);
    return memo[rest][in] = total;
}

int main() {
    cout << "    n       答案 f(n)      1.没记忆化    2.有记忆化  真正算的格子\n";
    cout << "-----   -------------   -------------   -----------   -----------\n";

    for (int k : {3, 5, 10, 13, 15, 16}) {
        n = k;
        naiveNodes = 0;
        long long ans = naive(k, 0);

        memset(memo, -1, sizeof memo);
        memoCalls = memoFilled = 0;
        withMemo(k, 0);

        cout << setw(5) << k
             << setw(16) << ans
             << setw(16) << naiveNodes
             << setw(14) << memoCalls
             << setw(14) << memoFilled << "\n";
    }

    cout << "\n最后一列正好是 n(n+1)/2（自己对一对：3->6, 5->15, 10->55, 16->136）——\n";
    cout << "因为能走到的状态就是 rest 取 1..n、in 取 0..n-rest，数一数就是这么多。\n";
    cout << "题目的上界 n = 18：第 1 列到那时是十亿量级，而最后一列只有 171 个格子。\n";
    return 0;
}