DP 入门：从记忆化到递推

// 爬楼梯 —— 朴素递归（第 1、2 章那个会超时的写法，这里再见一面）
//
// 题意：n 级台阶，每次能上 1 级或 2 级，一共有多少种走法？
//
// 递归三要素（第 1 章）：
//   出口：走到第 0 级（正好走完）算 1 种；走过头（负数）算 0 种。
//   分解：最后一步要么迈了 1 级，要么迈了 2 级 —— 于是 f(n) = f(n-1) + f(n-2)。
//   收敛：n 每次至少减 1，一定会到出口。
//
// 这份代码是对的，而且它是这一章所有优化的出发点。**先写得出它，再谈优化。**
//
// 它的问题只有一个：**同一个 f(k) 被算了无数遍**。
// 调用次数正好是斐波那契数列本身 —— n = 40 要算一亿多次，n = 45 要十几亿次。
//
// 输入：一个整数 n（这份代码只适合 n <= 45 左右，再大等不起）
// 输出：走法数
//
// ⚠ 答案增长得很快：n = 91 时是 7 540 113 804 746 346 429，已经顶到 long long 的上限；
//   n = 92 直接溢出成负数，**而且不会有任何报错**。本章可信的范围是 n <= 91。
//   真要算 n = 1000（洛谷 P1255），得写高精度。

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

long long f(int n) {
    if (n < 0) return 0;        // 走过头了，这条路不算数
    if (n == 0) return 1;       // 正好走完，算一种走法
    return f(n - 1) + f(n - 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

// 爬楼梯 —— 把三种写法各自「算了多少次」数出来
//
// 为什么要有这份代码：耗时会随机器变，**计算次数不会**。
// 想说清楚 DP 到底省掉了什么，数次数比看秒表可靠得多（第 16 章数搜索节点也是这个道理）。
//
// 三种写法数的是同一件事「函数体 / 循环体执行了几次」：
//   纯递归：solve(n) 每被调用一次算一次 —— 它等于 2·f(n+1) − 1，也就是斐波那契量级
//   记忆化：真正算过的状态数（查表命中不算）—— 最多 n+1 个
//   递推  ：循环体跑的次数 —— 正好 n−1 次
//
// 你会看到第二、三列几乎一样，而第一列在 n = 30 时已经是它们的十万倍。
// **这就是 DP 的全部价值：把「重复算」变成「算一次」。**
//
// 用法：直接运行，或者给一个参数指定最大的 n（默认 30，别超过 45 —— 第一列会爆炸）。

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

long long recCalls;
long long recSolve(int n) {
    recCalls++;
    if (n < 0) return 0;
    if (n == 0) return 1;
    return recSolve(n - 1) + recSolve(n - 2);
}

long long memoCalcs;
vector<long long> f;
vector<char> vis;
long long memoSolve(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (vis[n]) return f[n];        // 命中查表：不算「一次计算」
    memoCalcs++;                    // 真正算一次
    long long res = memoSolve(n - 1) + memoSolve(n - 2);
    vis[n] = 1;
    f[n] = res;
    return res;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    int maxN = (argc > 1) ? atoi(argv[1]) : 30;
    if (maxN < 1) maxN = 1;
    if (maxN > 45) maxN = 45;

    cout << "  n      纯递归调用次数   记忆化真正算的次数   递推循环次数   答案\n";
    for (int n = 1; n <= maxN; n++) {
        recCalls = 0;
        long long ans = recSolve(n);

        memoCalcs = 0;
        f.assign(n + 2, 0);
        vis.assign(n + 2, 0);
        memoSolve(n);

        long long loops = (n >= 2) ? n - 1 : 0;

        cout << setw(3) << n
             << setw(20) << recCalls
             << setw(21) << memoCalcs
             << setw(15) << loops
             << setw(22) << ans << "\n";
    }
    cout << "\n第一列是斐波那契量级，第二、三列是线性的。n 每加 1，第一列翻 1.6 倍，后两列加 1。\n";
    return 0;
}

// 爬楼梯 —— 递推填表，这就是「标准长相」的动态规划
//
// 把 stairsMemo.cpp 的递归**反过来**：不再是「要 f(n) 就去问 f(n-1)」，
// 而是「先把 f(0)、f(1) 填好，再顺着往上填」。
//
// ============ DP 三件套 ============
// 写任何一道 DP，先在草稿纸上把这三句话写出来，再动手敲代码：
//
//   【状态】f[i] = 走到第 i 级台阶的走法数
//           —— 一句人话，不带任何代码。说不出这句话就别往下写。
//   【转移】f[i] = f[i-1] + f[i-2]
//           —— 最后一步要么迈 1 级要么迈 2 级，两类互不重叠、也没有遗漏。
//   【边界和顺序】f[0] = 1, f[1] = 1；i 从小到大填。
//           —— ★ 顺序不是背的：f[i] 依赖 f[i-1] 和 f[i-2]，
//              它们的下标更小，所以必须先填小的。**依赖谁，就先填谁。**
//
// 复杂度 O(n)，空间 O(n)（下面还给了 O(1) 的版本）。
// 和记忆化算的东西一模一样，只是把「用到时再算」换成了「按顺序全算一遍」。
//
// 比记忆化好在哪：没有递归开销，而且**不会爆栈**（见 stairsDeep.cpp）。
// 代价是你必须自己想清楚填表顺序 —— 而这正是这一章要练的东西。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n >= 95) { cout << "n 开得太大了，这份代码只到 94\n"; return 0; }
    // ⚠ 只有 n <= 91 的答案是可信的：f(92) 超出 long long，会安静地变成负数（试试 92）。

    vector<long long> f(n + 2, 0);
    f[0] = 1;                       // 边界：站在原地，算一种走法
    if (n >= 1) f[1] = 1;

    for (int i = 2; i <= n; i++)    // ★ 从小到大填，因为 f[i] 依赖更小的下标
        f[i] = f[i - 1] + f[i - 2];

    cout << f[n] << "\n";

    // 顺带一提：f[i] 只用到前两格，所以整张表其实没必要留着 ——
    //   long long a = 1, b = 1;
    //   for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    //   答案就是 (n == 0 ? 1 : b);
    // 这叫**滚动数组**，空间从 O(n) 降到 O(1)。第 23 章的 01 背包会正式用到它，
    // 那里滚动不只是省空间，还牵扯到「循环该正序还是倒序」的经典坑。
    return 0;
}

// 记忆化 vs 递推：一个记忆化**做不到**、而递推轻松做到的事 —— 不爆栈
//
// 到目前为止，记忆化和递推看起来是一回事（算的东西一样、复杂度一样）。
// 这份代码演示它们唯一的实质差别：**递归有多深，栈就有多深。**
//
// 用法（在网页上就是「命令行参数」那一栏）：
//     ./stairsDeep memo 100000      ← 记忆化，递归 10 万层
//     ./stairsDeep dp   100000      ← 递推，同样的 n
//     ./stairsDeep memo 1000000     ← 递归 100 万层：**这里会直接崩掉**
//     ./stairsDeep dp   1000000     ← 递推：秒出
//
// 为了让 n 能开得很大又不溢出，这里对 1e9+7 取模（第 42 章会专门讲取模）。
// 取模不影响我们要看的东西：栈。
//
// 崩掉的时候你看到的是「段错误 / Segmentation fault」，**没有任何提示说是栈溢出**。
// 这是竞赛里最难查的一类错误之一：代码逻辑完全正确，数据一大就崩，
// 本地小数据还测不出来。记住这个场景，以后再遇到能省几个小时。
//
// 结论不是「记忆化不好」，而是：
//   **递归深度和数据规模同阶的时候，要么改递推，要么手动开大栈。**

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

const long long MOD = 1000000007;
vector<long long> f;
vector<char> vis;

long long solve(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (vis[n]) return f[n];
    long long res = (solve(n - 1) + solve(n - 2)) % MOD;
    vis[n] = 1;
    f[n] = res;
    return res;
}

int main(int argc, char** argv) {
    string mode = (argc > 1) ? argv[1] : "dp";
    int n = (argc > 2) ? atoi(argv[2]) : 100000;
    if (n < 0) n = 0;

    if (mode == "memo") {
        f.assign(n + 2, 0);
        vis.assign(n + 2, 0);
        cout << "记忆化（递归 " << n << " 层）… ";
        cout.flush();               // 先把这句冲出去，不然崩了什么都看不见
        cout << solve(n) << "\n";
    } else {
        vector<long long> g(n + 2, 0);
        g[0] = 1;
        if (n >= 1) g[1] = 1;
        for (int i = 2; i <= n; i++) g[i] = (g[i - 1] + g[i - 2]) % MOD;
        cout << "递推（循环 " << n << " 次）… " << g[n] << "\n";
    }
    return 0;
}

// 数字三角形 —— 从下往上填表（第 17 章结尾那四行，这里把它写完整）
//
// 输入输出和 code/17-memo-search/ 那几份完全一样，所以**可以直接拿第 17 章的
// brute.cpp 当标准答案、gen.cpp 当生成器来对拍**（对拍器是可以跨章节复用的）。
//
// ============ DP 三件套 ============
//   【状态】f[i][j] = 从第 i 行第 j 列出发，走到底边，能拿到的最大和
//   【转移】f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])
//   【边界和顺序】最后一行 f[n-1][j] = a[n-1][j]；
//                 i 从大到小填 —— ★ 因为 f[i][*] 依赖 f[i+1][*]，
//                 下面那一行必须先算好。**依赖谁，就先填谁。**
//
// 答案是 f[0][0]，不用再取 max ——「从 (0,0) 出发」本身就是题目要求的。
//
// 这个方向的好处：**没有边界判断**。每一格都老老实实有两个来源，
// 不像从上往下那样要单独伺候每行的头和尾（见 triUp.cpp）。
// 同一道题，换个填表方向，代码难度可以差一截 —— 这也是「顺序」值得单独讲一章的原因。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    // f 直接借用 a 的空间：算到第 i 行时，a[i+1][*] 里存的已经是 f[i+1][*] 了
    for (int i = n - 2; i >= 0; i--)               // ★ 从倒数第二行往上
        for (int j = 0; j <= i; j++)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);

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

// 数字三角形 —— 填表顺序写反了会怎样（这份代码是**故意错的**）
//
// 它和 triDown.cpp 只差一个字：外层循环写成了 `for (int i = 0; i < n - 1; i++)`，
// 也就是**从上往下**去填一个「依赖下一行」的状态。
//
// 于是每算一格 a[i][j]，读到的 a[i+1][*] 都还是**原始输入值**，而不是算好的 f[i+1][*]。
// 相当于只往下看了一层就下结论。
//
// ★ 这一章最该记住的一件事：
//   **填错顺序不会报错、不会崩、不会警告，只会安安静静给你一个错的答案。**
//   编译器不知道你的 f[i][j] 依赖谁，那是你脑子里的东西。
//
// 这份代码会把两种顺序都跑一遍，并排打给你看差多少：
//   正确顺序（从下往上）和错误顺序（从上往下），以及它们是不是一样。
// 小三角形上两者常常碰巧相等（层数少的时候「只看一层」和「看到底」没区别），
// 层数一多就必然不同 —— 这又是一次「错误的写法经常蒙对」（第 20 章）。
//
// 输入输出格式和 triDown.cpp 一样。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    auto right = a, bad = a;

    for (int i = n - 2; i >= 0; i--)              // 正确：从下往上
        for (int j = 0; j <= i; j++)
            right[i][j] += max(right[i + 1][j], right[i + 1][j + 1]);

    for (int i = 0; i < n - 1; i++)               // 错误：顺序反了
        for (int j = 0; j <= i; j++)
            bad[i][j] += max(bad[i + 1][j], bad[i + 1][j + 1]);

    cout << "正确顺序（从下往上）：" << right[0][0] << "\n";
    cout << "错误顺序（从上往下）：" << bad[0][0] << "\n";
    cout << (right[0][0] == bad[0][0]
                 ? "这组数据上两者**碰巧相等** —— 别高兴，换个大一点的三角形再试。\n"
                 : "两者不同。错误顺序读到的是还没填好的格子，等于只往下看了一层。\n");
    return 0;
}

// 数字三角形 —— 从上往下填表（同一道题，反着填）
//
// 为什么要写第二遍：**因为它更难写。**
// 对着 triDown.cpp 看，你会亲眼看到「填表方向」这个选择要付出什么代价。
//
// ============ DP 三件套 ============
//   【状态】g[i][j] = 从顶点 (0,0) 走到 (i,j)，路上能拿到的最大和
//           —— 注意这和 triDown.cpp 的状态**不是一回事**（那边是「从这里走到底边」）。
//              同一道题可以有好几种状态定义，选哪个决定了后面全部的难度。
//   【转移】g[i][j] = a[i][j] + max(g[i-1][j-1], g[i-1][j])
//   【边界和顺序】g[0][0] = a[0][0]；i 从小到大填（依赖上一行）。
//   【答案】最后一行的最大值 —— 不是 g[n-1][0]，因为终点可以是底边任意一格。
//
// ⚠ 代价一：**边界要单独伺候。**
//   每行最左边那格 (i,0) 只能从 (i-1,0) 来（左上方没有格子）；
//   最右边那格 (i,i) 只能从 (i-1,i-1) 来。
//   写漏了会读到没填过的格子 —— 不报错，只是答案错。
//
// ⚠ 代价二：**答案要多扫一遍**取最大值。
//
// triDown.cpp 一个 if 都不用写。所以：
// **选状态和填表方向的时候，先想想哪个方向的边界更少。**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> a(n), g(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        g[i].assign(i + 1, 0);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    g[0][0] = a[0][0];
    for (int i = 1; i < n; i++) {                  // ★ 从上往下，依赖上一行
        for (int j = 0; j <= i; j++) {
            if (j == 0)            g[i][j] = g[i - 1][j];            // 最左：只能从正上方来
            else if (j == i)       g[i][j] = g[i - 1][j - 1];        // 最右：只能从左上方来
            else                   g[i][j] = max(g[i - 1][j - 1], g[i - 1][j]);
            g[i][j] += a[i][j];
        }
    }

    long long best = g[n - 1][0];
    for (int j = 0; j <= n - 1; j++) best = max(best, g[n - 1][j]);   // 终点是底边任意一格
    cout << best << "\n";
    return 0;
}

// 数字三角形 —— 从下往上填表（第 17 章结尾那四行，这里把它写完整）
//
// 输入输出和 code/17-memo-search/ 那几份完全一样，所以**可以直接拿第 17 章的
// brute.cpp 当标准答案、gen.cpp 当生成器来对拍**（对拍器是可以跨章节复用的）。
//
// ============ DP 三件套 ============
//   【状态】f[i][j] = 从第 i 行第 j 列出发，走到底边，能拿到的最大和
//   【转移】f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])
//   【边界和顺序】最后一行 f[n-1][j] = a[n-1][j]；
//                 i 从大到小填 —— ★ 因为 f[i][*] 依赖 f[i+1][*]，
//                 下面那一行必须先算好。**依赖谁，就先填谁。**
//
// 答案是 f[0][0]，不用再取 max ——「从 (0,0) 出发」本身就是题目要求的。
//
// 这个方向的好处：**没有边界判断**。每一格都老老实实有两个来源，
// 不像从上往下那样要单独伺候每行的头和尾（见 triUp.cpp）。
// 同一道题，换个填表方向，代码难度可以差一截 —— 这也是「顺序」值得单独讲一章的原因。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    // f 直接借用 a 的空间：算到第 i 行时，a[i+1][*] 里存的已经是 f[i+1][*] 了
    for (int i = n - 2; i >= 0; i--)               // ★ 从倒数第二行往上
        for (int j = 0; j <= i; j++)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);

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

// 爬楼梯 —— 递推填表，这就是「标准长相」的动态规划
//
// 把 stairsMemo.cpp 的递归**反过来**：不再是「要 f(n) 就去问 f(n-1)」，
// 而是「先把 f(0)、f(1) 填好，再顺着往上填」。
//
// ============ DP 三件套 ============
// 写任何一道 DP，先在草稿纸上把这三句话写出来，再动手敲代码：
//
//   【状态】f[i] = 走到第 i 级台阶的走法数
//           —— 一句人话，不带任何代码。说不出这句话就别往下写。
//   【转移】f[i] = f[i-1] + f[i-2]
//           —— 最后一步要么迈 1 级要么迈 2 级，两类互不重叠、也没有遗漏。
//   【边界和顺序】f[0] = 1, f[1] = 1；i 从小到大填。
//           —— ★ 顺序不是背的：f[i] 依赖 f[i-1] 和 f[i-2]，
//              它们的下标更小，所以必须先填小的。**依赖谁，就先填谁。**
//
// 复杂度 O(n)，空间 O(n)（下面还给了 O(1) 的版本）。
// 和记忆化算的东西一模一样，只是把「用到时再算」换成了「按顺序全算一遍」。
//
// 比记忆化好在哪：没有递归开销，而且**不会爆栈**（见 stairsDeep.cpp）。
// 代价是你必须自己想清楚填表顺序 —— 而这正是这一章要练的东西。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n >= 95) { cout << "n 开得太大了，这份代码只到 94\n"; return 0; }
    // ⚠ 只有 n <= 91 的答案是可信的：f(92) 超出 long long，会安静地变成负数（试试 92）。

    vector<long long> f(n + 2, 0);
    f[0] = 1;                       // 边界：站在原地，算一种走法
    if (n >= 1) f[1] = 1;

    for (int i = 2; i <= n; i++)    // ★ 从小到大填，因为 f[i] 依赖更小的下标
        f[i] = f[i - 1] + f[i - 2];

    cout << f[n] << "\n";

    // 顺带一提：f[i] 只用到前两格，所以整张表其实没必要留着 ——
    //   long long a = 1, b = 1;
    //   for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    //   答案就是 (n == 0 ? 1 : b);
    // 这叫**滚动数组**，空间从 O(n) 降到 O(1)。第 23 章的 01 背包会正式用到它，
    // 那里滚动不只是省空间，还牵扯到「循环该正序还是倒序」的经典坑。
    return 0;
}