K07 动态规划二：网格 DP、区间 DP + 二叉树（第二轮系统课 · 第 7 次）

本次课 3 小时：前 30 分钟复盘 10/17 的整卷②，然后是两个模块，每个约 50 分钟。

〇、整卷②复盘（课上前 30 分钟）

同 K06 第〇节三个问题，再加一个：和整卷①比，哪个环节变快了？

一、M12 动态规划二

盲写（15 分钟，合上讲义）

输入 n、m 和一个 n×m 的数字网格（数字可能是负数），从左上角走到右下角，每步只能向右或向下，求经过的数字之和最大是多少。n、m ≤ 1000。

输入 3 3 / 1 -2 3 / 4 5 -6 / 7 8 9 → 输出 29

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

long long a[1005][1005], f[1005][1005];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) f[i][j] = a[i][j];                // 起点
            else if (i == 1) f[i][j] = f[i][j - 1] + a[i][j];       // 第一行只能从左边来
            else if (j == 1) f[i][j] = f[i - 1][j] + a[i][j];       // 第一列只能从上面来
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

⚠️ 有负数时，第一行、第一列必须单独处理。 如果偷懒让 f[0][j]、f[i][0] 都是 0 去参与 max，遇到全是负数的格子，就会从"网格外面"那个 0 转移过来——相当于凭空多出一条路。

1.1 网格 DP 的三种变形

📝 一条通用的检查法：f[i][j] 用到的格子，必须在它之前已经算好了。 只能向右、向下走，所以按行从上到下、每行从左到右算就行。如果题目允许向上走，这个顺序就不成立了——这正是方格取数难的地方，它是 T4。

1.2 区间 DP：石子合并

n 堆石子排成一排，每次合并相邻两堆，代价是两堆的总重量。合并成一堆的最小总代价是多少？

为什么不能贪心：每次合并最小的相邻两堆？L05 数字三角形讲过，局部最优不等于全局最优。

三件套：

1. 状态：f[l][r] = 把第 l 堆到第 r 堆合并成一堆的最小代价
2. 转移：最后一次合并，一定是把 [l, k] 和 [k+1, r] 两大堆合起来。枚举分界点 k： f[l][r] = min( f[l][k] + f[k+1][r] ) + (第 l 到 r 堆的总重量)
3. 初始：f[i][i] = 0（一堆不用合并）

⚠️ 循环顺序是区间 DP 的关键：算 f[l][r] 要用到更短的区间，所以外层枚举区间长度，从 2 到 n。

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

int a[305], s[305], f[305][305];

int main() {
    int n;
    cin >> n;
    // n<=300，三重循环 O(n^3)=2.7e7，能过
    for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; }   // 前缀和，O(1) 求区间总重
    for (int len = 2; len <= n; len++) {                // 外层：区间长度
        for (int l = 1; l + len - 1 <= n; l++) {        // 中层：左端点
            int r = l + len - 1;
            f[l][r] = INT_MAX;
            for (int k = l; k < r; k++)                 // 内层：最后一次合并的分界点
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
            f[l][r] += s[r] - s[l - 1];
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

⚠️ n = 1 时外层循环一次都不进，直接输出 f[1][1] = 0。这组数据正好检查边界。

📝 区间 DP 的"长相"：题目说"相邻的合并""从两头取""回文"，状态就是 f[l][r]。三重循环的顺序永远是：长度 → 左端点 → 分界点。

二、M13 二叉树

盲写（15 分钟，合上讲义）

输入 n（n ≤ 1000），接下来第 i 行两个数，是结点 i 的左孩子和右孩子编号（0 表示没有）。根是 1。输出前序、中序、后序遍历（各一行）和树的深度。

输入 5 / 2 3 / 4 5 / 0 0 / 0 0 / 0 0 → 输出 1 2 4 5 3 / 4 2 5 1 3 / 4 5 2 3 1 / 3

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

int lc[1005], rc[1005];

void pre(int u)  { if (!u) return; cout << u << " "; pre(lc[u]); pre(rc[u]); }   // 根 左 右
void in_(int u)  { if (!u) return; in_(lc[u]); cout << u << " "; in_(rc[u]); }   // 左 根 右
void post(int u) { if (!u) return; post(lc[u]); post(rc[u]); cout << u << " "; } // 左 右 根

int depth(int u) {
    if (!u) return 0;
    return max(depth(lc[u]), depth(rc[u])) + 1;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lc[i] >> rc[i];
    pre(1);  cout << endl;
    in_(1);  cout << endl;
    post(1); cout << endl;
    cout << depth(1) << endl;
    return 0;
}

📝 三种遍历只差"输出自己"那一句放在哪：放最前是前序，放中间是中序，放最后是后序。

2.1 存储方式

⚠️ 完全二叉树的编号公式要求根是 1。 根从 0 开始时变成 2i+1、2i+2，初赛最爱考这个区别。

⚠️ 树很深时（比如 n = 10⁶ 且是一条链），递归深度 10⁶，本地 Dev-C++ 会栈溢出崩溃。 评测机栈通常开得很大，但本地测不了最大数据。课堂题 P4913 就是 n ≤ 10⁶——本地崩了不代表评测机也崩，这是 F2 里"本地和评测机不一样"的又一个例子。

2.2 由前序 + 中序还原后序

已知两种遍历，能唯一确定一棵树（其中一种必须是中序）。以前序 ABDEC、中序 DBEAC 为例：

1. 前序第一个就是根：A
2. 在中序里找到根：DBE A C——A 左边 DBE 是左子树，右边 C 是右子树
3. 左子树有 3 个结点，所以前序里 A 后面的 3 个 BDE 是左子树的前序，剩下的 C 是右子树的前序
4. 对左、右子树递归做同样的事
5. 后序 = 左子树后序 + 右子树后序 + 根

手推结果：左子树（前序 BDE、中序 DBE）的后序是 DEB，右子树是 C，所以整棵树后序是 DEBCA。

📝 写成代码就是一个递归函数 solve(前序串, 中序串)：用 find 在中序里找根的位置 k，再用 substr 切出左右两段。K01 的字符串工具箱全用得上。这是课堂题 P1827，自己写。

三、课堂题

四、本周作业（10/19–10/23，每天 1 道）

10/24（六）08:30–12:00 整卷③ NOIP2017 普及组——彩排，完全按考场规程走（F2 这周发）。

五、30 秒自测

1. 网格 DP 有负数时，第一行、第一列为什么要单独处理？
2. 区间 DP 的三重循环分别枚举什么？为什么外层是长度？
3. 前、中、后序遍历的代码差在哪？
4. 完全二叉树（根为 1）结点 i 的左孩子、右孩子、父亲编号？
5. 已知前序和中序，怎么找根、怎么分左右子树？

本次打卡：M12 ①、M13 ①（两道盲写）；作业 AC 后打 ②③。