记忆化搜索：从递归通向 DP 的那座桥

// 数字三角形 —— 暴力：纯递归，每条路都走一遍
//
// 输入：第一行 n，接下来 n 行，第 i 行有 i 个整数
// 输出：从顶端走到底端，每步只能走到「正下方」或「右下方」，路径上数字之和的最大值
//
// 例如：
//        7
//      3   8
//    8   1   0
//  2   7   4   4
// 最大和是 7 + 3 + 8 + 7 = 25
//
// 这个递归写得非常自然，几乎是把题目念了一遍：
//   best(i,j) = 从格子 (i,j) 出发走到底，能拿到的最大和
//             = a[i][j] + max( best(i+1, j), best(i+1, j+1) )
// 出口：最后一行哪儿也去不了，best = a[i][j] 自己。
//
// 思路完全正确。问题是它慢得离谱：每个格子都要往下分出两个叉，
// 一共 2^(n-1) 条路径，总调用次数是 2^n - 1。
// n = 30 时是十亿七千万次 —— 而这个三角形一共才 465 个格子。
//
// 慢在哪？慢在「重复计算」。看 best(2,1)：
//   从 (0,0) 走到 (2,1) 有两条路（先左后右、先右后左），
//   于是 best(2,1) 会被完完整整地重算两遍。
//   而它下面的每个格子，又会因此被多算一倍……越往下重复得越离谱。
// 拿 trace.cpp 跑一下，你能亲眼看到每个格子被调用了多少次 —— 正好是一个杨辉三角。

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

int n;
vector<vector<long long>> a;

long long best(int i, int j) {
    if (i == n - 1) return a[i][j];                    // 出口：已经在最后一行
    return a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));
}

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

    cout << best(0, 0) << "\n";
    return 0;
}

// 数字三角形 —— 数一数每个格子到底被算了多少次
//
// 用小一点的 n 跑（10 ~ 16 都行），看输出的那张「调用次数表」。
// 你会看到一个杨辉三角：第 i 行第 j 列的格子被调用了 C(i,j) 次。
//
// 最底下一行中间的那个格子，调用次数是整张表里最大的。
// n = 20 时它会被重复计算十几万次 —— 每一次算出来的结果都一模一样。
//
// 看完这张表，「加个数组把算过的存起来」就不是什么需要背的技巧了，
// 而是任何人看到这么多重复都会立刻想到的事。

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

int n;
vector<vector<long long>> a;
vector<vector<long long>> cnt;    // cnt[i][j] = best(i,j) 被调用了几次
long long totalCalls = 0;

long long best(int i, int j) {
    cnt[i][j]++;
    totalCalls++;
    if (i == n - 1) return a[i][j];
    return a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));
}

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

    long long ans = best(0, 0);

    cout << "答案 = " << ans << "\n\n";
    cout << "每个格子被调用的次数：\n";
    for (int i = 0; i < n; i++) {
        cout << string((n - i) * 4, ' ');
        for (int j = 0; j <= i; j++) printf("%8lld", cnt[i][j]);
        cout << "\n";
    }

    long long cells = (long long)n * (n + 1) / 2;
    cout << "\n格子总数     = " << cells << "\n";
    cout << "实际调用次数 = " << totalCalls << "\n";
    cout << "白算了       = " << (totalCalls - cells) << " 次"
         << "（占 " << fixed << setprecision(1)
         << (totalCalls ? 100.0 * (totalCalls - cells) / totalCalls : 0.0) << "%）\n";
    cout << "\n记忆化要做的，就是把这 " << (totalCalls - cells) << " 次白算全部省掉。\n";
    return 0;
}

// 数字三角形 —— 记忆化搜索
//
// 和 brute.cpp 解同一道题，答案必须一样。
// 但 n = 27 时暴力要跑一秒多，它只要几微秒。
//
// 关键的那一步想法 —— 而且这一步小得让人不敢相信：
//
//   best(i,j) 的答案，只跟 (i,j) 有关。
//   不管你是从哪条路摸到 (2,1) 的，best(2,1) 永远是同一个数。
//   既然如此，第一次算出来之后把它记下来，
//   下次再问到 (2,1)，直接把记下的值还回去就行了 —— 不用再往下递归。
//
//   于是每个格子最多只会被真正计算一次。
//   格子一共 n(n+1)/2 个，所以复杂度从 O(2^n) 一下掉到 O(n²)。
//
// 相比 brute.cpp，代码只多了三行：一个 f 数组、一个 vis 数组、一个「查表就返回」。
// 算法思想没变，递归结构没变，改的只是「别重复算」。
//
// 这就是「记忆化搜索」，它是从递归通向动态规划的那座桥：
//   你先按最自然的方式写出递归（这一步靠的是把题目念清楚），
//   再加一张表把结果存起来（这一步是纯机械的）。
//   等你熟练之后，会发现把递归改写成「从底往上填表」的循环，就是所谓的 DP。
//   但顺序永远是：先会递归，再会记忆化，最后才是 DP。反过来学，必卡。

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

int n;
vector<vector<long long>> a;
vector<vector<long long>> f;      // f[i][j] = best(i,j) 算出来的结果
vector<vector<char>> vis;         // vis[i][j] = 这一格算过了没有

long long best(int i, int j) {
    if (vis[i][j]) return f[i][j];      // ★ 查表命中，直接还回去，不再往下递归

    long long res;
    if (i == n - 1) res = a[i][j];                                    // 出口
    else res = a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));     // 和暴力一模一样

    vis[i][j] = 1;                      // ★ 算完之后才记下来
    f[i][j] = res;
    return res;
}
// 记忆化的标准骨架就是这三段：开头查表 → 中间照抄暴力 → 结尾存表。
// 注意「存表」要放在算完之后，不要放在算之前 —— 养成这个习惯，
// 以后遇到状态之间可能互相依赖的题目才不会踩坑。

int main() {
    if (!(cin >> n)) return 0;
    a.assign(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.assign(n, vector<long long>(n + 1, 0));
    vis.assign(n, vector<char>(n + 1, 0));

    cout << best(0, 0) << "\n";
    return 0;
}

// 数字三角形 —— 记忆化搜索
//
// 和 brute.cpp 解同一道题，答案必须一样。
// 但 n = 27 时暴力要跑一秒多，它只要几微秒。
//
// 关键的那一步想法 —— 而且这一步小得让人不敢相信：
//
//   best(i,j) 的答案，只跟 (i,j) 有关。
//   不管你是从哪条路摸到 (2,1) 的，best(2,1) 永远是同一个数。
//   既然如此，第一次算出来之后把它记下来，
//   下次再问到 (2,1)，直接把记下的值还回去就行了 —— 不用再往下递归。
//
//   于是每个格子最多只会被真正计算一次。
//   格子一共 n(n+1)/2 个，所以复杂度从 O(2^n) 一下掉到 O(n²)。
//
// 相比 brute.cpp，代码只多了三行：一个 f 数组、一个 vis 数组、一个「查表就返回」。
// 算法思想没变，递归结构没变，改的只是「别重复算」。
//
// 这就是「记忆化搜索」，它是从递归通向动态规划的那座桥：
//   你先按最自然的方式写出递归（这一步靠的是把题目念清楚），
//   再加一张表把结果存起来（这一步是纯机械的）。
//   等你熟练之后，会发现把递归改写成「从底往上填表」的循环，就是所谓的 DP。
//   但顺序永远是：先会递归，再会记忆化，最后才是 DP。反过来学，必卡。

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

int n;
vector<vector<long long>> a;
vector<vector<long long>> f;      // f[i][j] = best(i,j) 算出来的结果
vector<vector<char>> vis;         // vis[i][j] = 这一格算过了没有

long long best(int i, int j) {
    if (vis[i][j]) return f[i][j];      // ★ 查表命中，直接还回去，不再往下递归

    long long res;
    if (i == n - 1) res = a[i][j];                                    // 出口
    else res = a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));     // 和暴力一模一样

    vis[i][j] = 1;                      // ★ 算完之后才记下来
    f[i][j] = res;
    return res;
}
// 记忆化的标准骨架就是这三段：开头查表 → 中间照抄暴力 → 结尾存表。
// 注意「存表」要放在算完之后，不要放在算之前 —— 养成这个习惯，
// 以后遇到状态之间可能互相依赖的题目才不会踩坑。

int main() {
    if (!(cin >> n)) return 0;
    a.assign(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.assign(n, vector<long long>(n + 1, 0));
    vis.assign(n, vector<char>(n + 1, 0));

    cout << best(0, 0) << "\n";
    return 0;
}