课堂复习笔记：搜索与线性 DP

---

0. 今日知识地图

模块	对应题目	核心方法
DFS 搜索	迷宫出口	四方向扩展 + vis 标记
LIS 基础	最长上升子序列	f[i] 表示以 i 结尾的最长长度
LIS 变形	最大上升子序列和	长度改成“最大和”
LIS 应用	最少修改次数	保留最长上升子序列，其余修改
排序 + LIS	友好城市	先按一岸排序，再对另一岸求 LIS
LCS	最长公共子序列 / 挑选糖果	二维 DP 比较两个序列
双向 LIS	登山 / 合唱队形	正向上升 + 反向下降，拼成山峰
下降序列	怪盗基德的滑翔翼	从左或从右找最长下降路径
LIS 优化	最长上升子序列 2	贪心 + 二分，O(n log n)

---

一、DFS：迷宫出口

1. 题型特征

给一个 n × n 迷宫：

• 0 表示可以走
• 1 表示障碍
• 从起点走到终点
• 每次只能走上下左右四个方向

要求判断能不能到达终点。

---

2. 核心思路

用 DFS 从起点开始扩展。

每到一个格子，就尝试走四个方向：

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

判断新位置是否合法：

1. 没有越界
2. 不是障碍
3. 没有走过

如果合法，就标记并继续 DFS。

---

3. 关键模板

void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n
            && a[nx][ny] == 0 && vis[nx][ny] == 0) {
            vis[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}

---

4. 易错点

• 起点、终点如果是障碍，直接输出 NO。
• 起点也要先标记：

vis[sx][sy] = 1;

• DFS 结束后，看 vis[ex][ey] 是否为 1。

---

二、LIS：最长上升子序列

1. 题型特征

给一个序列，要求选出若干个数：

• 不改变原来的相对顺序
• 后面的数严格大于前面的数
• 求最多能选几个

注意：

子序列不要求连续，只要求顺序不变。

---

2. 状态定义

f[i] = 以第 i 个数结尾的最长上升子序列长度

初始化：

f[i] = 1;

因为只选自己，也是一条长度为 1 的上升子序列。

---

3. 状态转移

枚举前面的每个位置 j：

if (a[j] < a[i]) {
    f[i] = max(f[i], f[j] + 1);
}

含义：

如果 a[j] < a[i]，那么可以把 a[i] 接在以 j 结尾的上升子序列后面。

---

4. 答案

ans = max(ans, f[i]);

完整核心：

for (int i = 1; i <= n; i++) {
    f[i] = 1;
    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

复杂度：O(n^2)。

---

三、最大上升子序列和

1. 和普通 LIS 的区别

普通 LIS 求的是：

最多选几个数。

最大上升子序列和求的是：

选出来的上升子序列，数字总和最大是多少。

---

2. 状态定义

f[i] = 以第 i 个数结尾的最大上升子序列和

初始化：

f[i] = a[i];

因为只选自己，和就是 a[i]。

---

3. 状态转移

if (a[j] < a[i]) {
    f[i] = max(f[i], f[j] + a[i]);
}

答案：

ans = max(ans, f[i]);

---

4. 对比记忆

问题	f[i] 含义	初始化	转移
LIS 长度	以 i 结尾的最长长度	1	f[j] + 1
最大上升子序列和	以 i 结尾的最大和	a[i]	f[j] + a[i]

---

四、最少修改次数

1. 题目本质

要把序列改成严格递增，问最少修改几个数。

关键想法：

已经能构成严格递增子序列的数，可以保留下来。
剩下不能保留的数，就需要修改。

所以：

答案 = n - LIS长度

---

2. 复习重点

这题不是重新设计 DP，而是识别模型：

• 求最多能保留多少个数：LIS
• 求最少改多少个数：总数减去最多保留数

cout << n - ans;

---

五、友好城市：排序 + LIS

1. 题型特征

每条线连接两个城市，如果两条线交叉，就不能同时选。

给出很多对坐标，要求最多选多少条不交叉的线。

---

2. 核心转化

先按一边坐标排序。

sort(ab + 1, ab + n + 1, cmp);

排序后，问题变成：

在另一边坐标中，选出最长上升子序列。

---

3. 为什么能转化成 LIS？

如果按南岸坐标从小到大排序：

• 南岸顺序已经固定
• 要想线不交叉，北岸坐标也必须递增

所以对北岸坐标求 LIS。

---

4. 核心代码

sort(ab + 1, ab + n + 1, cmp);

for (int i = 1; i <= n; i++) {
    f[i] = 1;
    for (int j = 1; j < i; j++) {
        if (ab[j].b < ab[i].b) {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = max(ans, f[i]);
}

---

六、LCS：最长公共子序列

1. 题型特征

给两个序列或字符串，求它们相同的最长子序列长度。

今日对应：

• 最长公共子序列 1
• 挑选糖果

---

2. 状态定义

f[i][j] = 第一个序列前 i 个元素 和 第二个序列前 j 个元素 的 LCS 长度

---

3. 状态转移

如果当前两个元素相同：

f[i][j] = f[i - 1][j - 1] + 1;

如果不同：

f[i][j] = max(f[i - 1][j], f[i][j - 1]);

完整核心：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (a[i] == b[j]) {
            f[i][j] = f[i - 1][j - 1] + 1;
        } else {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
}

答案：

cout << f[n][m];

---

4. 字符串写法提醒

如果是字符串，为了从 1 开始编号，可以这样处理：

s1 = " " + s1;
s2 = " " + s2;

这样 s1[1] 就是第一个字符。

---

七、登山 / 合唱队形：双向 LIS

1. 题型特征

要求形成一个“先上升，后下降”的形状：

低 低 高 低 低

也就是：

左边严格上升，右边严格下降

这种题通常要枚举每个位置作为山顶。

---

2. 两个状态

正向：

f1[i] = 以 i 结尾，从左往右的 LIS 长度

反向：

f2[i] = 以 i 开始，从右往左看的下降序列长度

或者理解成：

从 i 往右走，能形成多长的下降序列。

---

3. 拼接答案

如果第 i 个位置作为山顶：

f1[i] + f2[i] - 1

为什么减 1？

因为山顶 i 被左右两边都算了一次。

ans = max(ans, f1[i] + f2[i] - 1);

---

4. 登山 vs 合唱队形

题目	问什么	答案
登山	最多保留多少个景点	ans
合唱队形	最少出列多少人	n - ans

---

八、怪盗基德的滑翔翼

1. 题型特征

从某栋楼开始，只能往一个方向滑，并且只能从高楼滑到低楼。

也就是要求：

• 向左方向的最长下降序列
• 向右方向的最长下降序列

取最大值。

---

2. 复习重点

这题不要只算一个方向。

因为题目允许一开始选择方向：

可以向左，也可以向右

所以要分别算两边，再取最大。

---