Accepted · 搜索/ 2.1 → 2.4

第二部分 · PART 2

搜索

搜索是铜牌的核心考点之一，而且它直接建立在你已经掌握的递归（DFS）和队列（BFS）之上——承接得非常自然。

从 DFS/BFS 两大基础搜索，到回溯（枚举所有方案）、剪枝（让指数暴力变可行），再到记忆化搜索——它既是搜索的终点，又是动态规划的起点。这一部分走完，你就摸到 DP 的门了。

第二部分 · 2.1

2.1 DFS / BFS

教教练衔接coach

正式进入 第二部分：搜索！搜索是铜牌的核心考点之一，而且它直接建立在你已经掌握的递归（1.6）和队列（1.7）之上——DFS 就是递归，BFS 就是队列，承接得非常自然。这一节先把 DFS 和 BFS 这两大基础搜索打通。

先用一句话抓住两者的区别和联系：

搜索 = 系统地"试遍"所有可能的状态/路径，直到找到答案。
DFS（深度优先）：一条路走到黑，撞墙了再回头换路。用递归/栈实现。
BFS（广度优先）：一层一层向外扩展，像水波纹扩散。用队列实现。

一、先理解"图"和"状态"的概念

搜索的对象通常是图或状态空间。先建立直觉：

图：由节点和边组成。比如地图上的城市（节点）和道路（边），或者迷宫里的格子（节点）和相邻关系（边）。
状态：问题在某一时刻的"样子"。比如迷宫里你当前所在的格子就是一个状态，从一个状态能转移到相邻状态。
搜索：就是从起始状态出发，沿着边/转移，探索所有能到达的状态，找到目标。

很多搜索题不会明说"这是图"，但你要能看出来——迷宫、棋盘、状态转移，本质都是在图上搜索。

二、DFS（深度优先搜索）—— 一条路走到黑

核心思想

从一个节点出发，沿着一条路径尽可能深入，直到无路可走（撞墙或到终点），然后回退（回溯）到上一个分叉，换另一条路继续。本质是递归（接 1.6）。

DFS 的两种典型场景

场景 A：遍历图/网格（访问所有能到的节点） 场景 B：枚举所有方案（全排列、子集等，这是 2.2 回溯的内容，下节细讲）

这节先讲场景 A：在网格/图上 DFS。

例题精讲：岛屿数量（网格 DFS 经典）

题意：一个 n×m 的网格，1 是陆地、0 是水。相邻（上下左右）的陆地连成一个岛屿。求岛屿的数量。

sample.txt

输入网格:
1 1 0 0
1 0 0 1
0 0 1 1
答案: 2  （左上一块，右下一块）

思路：遍历每个格子，遇到没访问过的陆地 1，岛屿数 +1，然后用 DFS 把这块岛屿的所有相连陆地全部标记为已访问（"淹掉"），这样同一岛屿不会被重复计数。

solution.cpp

const int N = 1005;
int n, m;
int g[N][N];           // 网格
bool vis[N][N];        // 是否访问过

// 四个方向：上下左右（dx[i], dy[i] 表示第 i 个方向的行列变化）
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y) {
    vis[x][y] = true;              // 标记当前格子已访问
    for (int i = 0; i < 4; i++) {  // 尝试四个方向
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 新格子：没越界 + 是陆地 + 没访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && g[nx][ny] == 1 && !vis[nx][ny]) {
            dfs(nx, ny);           // 递归访问相邻陆地
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 1 && !vis[i][j]) {  // 遇到新岛屿
                cnt++;
                dfs(i, j);          // 淹掉整块岛屿
            }
    cout << cnt << "\n";
    return 0;
}

关键点拆解：

方向数组 dx/dy：用 {-1,1,0,0} 和 {0,0,-1,1} 表示上下左右四个方向，循环 i=0~3 就能遍历四个方向。这是网格搜索的标准写法，务必记住，比写四个 if 简洁。
vis 标记数组：防止重复访问（陷入死循环）。这是搜索防止无限循环的关键。
边界检查：nx >= 0 && nx < n && ny >= 0 && ny < m，防止越界（接 0.3）。

DFS 网格模板的三件套：①方向数组 ②vis标记 ③边界检查。岛屿、连通块、洪水填充（flood fill）都是这个模板。

DFS 用栈的非递归写法（了解）

DFS 本质是递归（用系统栈），也可以用显式栈手动实现，避免递归过深爆栈（接 1.6）。铜牌阶段递归写法够用，知道能用栈改写即可。

三、BFS（广度优先搜索）—— 一层层扩散

核心思想

从起点出发，先访问所有距离为 1 的节点，再访问距离为 2 的，再距离为 3 的…… 像水波纹一样一圈圈向外扩展。用队列实现（接 1.7）。

BFS 最重要的特性：求最短路径

BFS 天然能求"最少步数/最短路径"（在边权都相同的图上）。因为它是一层层扩展的，第一次到达某个节点时，走过的步数一定是最少的。

这是 BFS 相比 DFS 的核心优势——迷宫求最短路、最少操作次数，都用 BFS。

例题精讲：迷宫最短路径（BFS 经典）

题意：n×m 迷宫，0 可走、1 是墙。从起点 (0,0) 到终点 (n-1,m-1)，每次走上下左右一格，求最少步数（走不到输出 -1）。

solution.cpp

const int N = 1005;
int n, m;
int g[N][N];
bool vis[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs() {
    queue<pair<int,int>> q;        // 队列存坐标
    q.push({0, 0});
    vis[0][0] = true;
    int step = 0;                  // 步数（层数）

    while (!q.empty()) {
        int sz = q.size();         // 当前层有多少个节点
        for (int s = 0; s < sz; s++) {   // 处理完整一层
            auto [x, y] = q.front();
            q.pop();
            if (x == n-1 && y == m-1) return step;  // 到终点，返回步数

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m
                    && g[nx][ny] == 0 && !vis[nx][ny]) {
                    vis[nx][ny] = true;   // 入队时就标记！（重要）
                    q.push({nx, ny});
                }
            }
        }
        step++;                    // 处理完一层，步数+1
    }
    return -1;                      // 队列空了还没到终点，不可达
}

关键点拆解：

队列存状态：这里状态是坐标 (x,y)，用 queue<pair<int,int>>。
按层处理：int sz = q.size() 记录当前层节点数，内层循环处理完一整层后 step++。这样能精确统计步数（层数）。
入队时标记 vis（极重要的易错点）：必须在入队的时候就标记 vis[nx][ny]=true，而不是出队时标记。否则同一个节点可能被多次入队（不同节点都指向它），导致重复和错误。记住：BFS 入队即标记。
第一次到终点就是最短：因为 BFS 一层层扩展，到达终点时的 step 就是最少步数。

BFS 网格模板的要点：①队列存状态 ②入队即标记vis ③按层统计步数 ④第一次到目标即最优。

BFS 求步数的另一种写法（记录距离）

除了"按层"，也可以用一个 dist 数组记录到每个点的步数，更通用：

solution.cpp

int dist[N][N];              // dist[x][y] = 从起点到(x,y)的最少步数
memset(dist, -1, sizeof(dist));   // -1 表示没访问
dist[0][0] = 0;
queue<pair<int,int>> q;
q.push({0, 0});
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (合法 && dist[nx][ny] == -1) {   // 没访问过
            dist[nx][ny] = dist[x][y] + 1;  // 步数 = 上一个 +1
            q.push({nx, ny});
        }
    }
}
// dist[n-1][m-1] 就是答案（-1 表示不可达）

这种写法更灵活（随时能查到任意点的距离），推荐这种，不用手动按层。

四、DFS vs BFS：怎么选（关键判断）

	DFS（深度优先）	BFS（广度优先）
实现	递归 / 栈	队列
特点	一条路走到黑	一层层扩展
求最短路	❌ 不保证最短	✅ 天然最短（边权相同）
空间	O(深度)	O(宽度，可能很大)
适合	遍历所有节点/方案、连通性、枚举	最少步数、最短路径、层级关系

怎么选：

求"最少步数 / 最短路径 / 最少操作" → BFS（这是 BFS 的招牌）。
求"有多少连通块 / 能否到达 / 遍历所有 / 枚举所有方案" → DFS（更简洁）。
判断连通性（两点是否相连）→ 两者都行，DFS 代码更短。

记忆口诀：最短路用 BFS，数连通块/枚举方案用 DFS。 看到"最少""最短""最快"就想 BFS。

五、搜索的通用要素（DFS/BFS 都适用）

写任何搜索，想清楚这几点：

状态是什么：用什么表示一个"位置/局面"（坐标？数组？）。
起点和终点：从哪开始，到哪结束。
状态转移：从一个状态能到哪些状态（方向数组、合法移动）。
判重（vis）：怎么标记访问过的状态，防止重复/死循环。这是搜索不挂的关键。
边界检查：合法性判断（越界、撞墙等）。

六、本节速记卡

DFS：一条路走到黑，递归实现。网格三件套：方向数组 + vis标记 + 边界检查。用于数连通块、遍历、枚举。
BFS：一层层扩散，队列实现。天然求最短路/最少步数。要点：入队即标记vis、用dist数组记录步数。
方向数组：dx[]={-1,1,0,0}, dy[]={0,0,-1,1}，网格搜索标配。
选择：最短/最少→BFS；连通块/枚举/可达性→DFS。
核心：vis 判重防死循环，边界检查防越界。

这节是搜索的地基。DFS 和 BFS 的网格模板（岛屿数量、迷宫最短路）是铜牌高频题型，务必把这两个模板写到滚瓜烂熟——尤其是方向数组、vis 判重、BFS 入队即标记这几个点。很多搜索题就是这俩模板换个皮。

承上启下：你会发现 DFS 就是 1.6 的递归换了个应用场景，BFS 就是 1.7 的队列的核心用途。前面打的基础在这里直接变现。

下一节 2.2 回溯，是 DFS 的另一大应用——枚举所有方案（全排列、子集、组合），它会把 DFS 用在"暴力搜索所有可能"上，是偷分（接 0.8 暴力）和解决小数据题的利器。

教教练衔接coach

要不要我出几道 DFS/BFS 的题（岛屿/连通块类 DFS、迷宫最短路类 BFS）巩固这两个核心模板？还是直接推进 2.2 回溯？

配套练习题

好，给你 6 道题巩固 2.1，DFS（连通块/遍历）和 BFS（最短路）各三道，难度从模板到变体。这些都是铜牌高频题型，把模板练熟很重要。

老规矩：先自己写，重点想清楚"该用 DFS 还是 BFS、状态怎么表示、vis 怎么判重",再展开对照。

第 1 题：岛屿数量（DFS —— 模板裸题）

题意：n×m 网格，1 是陆地、0 是水，上下左右相邻的陆地算一个岛屿。求岛屿数量。

sample.txt

考点：网格 DFS 模板。遍历每个格子，遇到未访问的陆地就计数+1并 DFS 淹掉整块。三件套：方向数组、vis、边界检查。

AC第 1 题参考（岛屿数量）▸

solution.cpp

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

const int N = 1005;
int n, m, g[N][N];
bool vis[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && g[nx][ny] == 1 && !vis[nx][ny])
            dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 1 && !vis[i][j]) { cnt++; dfs(i, j); }
    cout << cnt << "\n";
    return 0;
}

要点：标准网格DFS模板。遇新陆地计数+DFS淹没。

第 2 题：最大岛屿面积（DFS —— 变体，求连通块大小）

题意：同上网格，求面积最大的岛屿包含多少个陆地格子（面积=格子数）。

sample.txt

（左上岛屿3个格子，右下岛屿3个格子，最大面积3）

考点：DFS 求连通块大小。让 dfs 返回（或累加）当前连通块的格子数，遍历时取最大值。练习"DFS 统计连通块大小"。

提示：dfs 可以返回这块岛屿的格子数：return 1 + 四个方向递归的和。或者用全局变量累加。

AC第 2 题参考（最大岛屿面积）▸

solution.cpp

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

const int N = 1005;
int n, m, g[N][N];
bool vis[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int dfs(int x, int y) {
    vis[x][y] = true;
    int area = 1;                  // 当前格子算1
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && g[nx][ny] == 1 && !vis[nx][ny])
            area += dfs(nx, ny);   // 累加相邻陆地的面积
    }
    return area;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];
    int maxArea = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 1 && !vis[i][j])
                maxArea = max(maxArea, dfs(i, j));  // 取最大面积
    cout << maxArea << "\n";
    return 0;
}

要点：dfs 返回连通块大小——1 + 四个方向递归的和。每块岛屿求面积，取max。"DFS返回连通块大小"是常用技巧。

第 3 题：被包围的区域（DFS —— 变体，边界思维）

题意：n×m 网格由 O 和 X 组成。找出所有被 X 完全包围的 O 区域，把它们变成 X。注意：与边界相连的 O 不算被包围（边界上的O以及通过O能连到边界的，都保留）。输出处理后的网格。

sample.txt

输入样例
4 4
X X X X
X O O X
X X O X
X O X X

输出样例
X X X X
X X X X
X X X X
X O X X

（中间的O被包围了变X；左下角的O在边界上，保留）

考点：经典的"边界反向思维"。直接找"被包围的O"很难，反过来：从边界上的所有O出发 DFS，标记所有"与边界相连的O"（这些是安全的），剩下没被标记的O就是被包围的，变成X。这是搜索的一种重要思维——从边界/外部入手。

提示：① 遍历四条边界，对边界上的每个O做DFS，标记为安全（比如改成临时字符'#'）；② 遍历整个网格，'#'还原成'O'，剩下的'O'改成'X'。

AC第 3 题参考（被包围的区域）▸

solution.cpp

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

const int N = 1005;
int n, m;
char g[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void dfs(int x, int y) {
    g[x][y] = '#';                 // 标记为安全（与边界相连）
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 'O')
            dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];

    // 从四条边界的O出发，标记所有与边界相连的O为安全
    for (int i = 0; i < n; i++) {
        if (g[i][0] == 'O') dfs(i, 0);
        if (g[i][m-1] == 'O') dfs(i, m-1);
    }
    for (int j = 0; j < m; j++) {
        if (g[0][j] == 'O') dfs(0, j);
        if (g[n-1][j] == 'O') dfs(n-1, j);
    }

    // 还原：'#'变回'O'（安全），剩下的'O'变'X'（被包围）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '#') g[i][j] = 'O';
            else if (g[i][j] == 'O') g[i][j] = 'X';
            cout << g[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

要点：反向思维——不直接找被包围的，而是从边界DFS标记"安全的O"，剩下的就是被包围的。这种"从边界/外部入手"是搜索的重要技巧。

第 4 题：迷宫最短路径（BFS —— 模板裸题）

题意：n×m 迷宫，0 可走、1 是墙。从 (0,0) 到 (n-1,m-1)，上下左右移动，求最少步数，不可达输出 -1。

sample.txt

输入样例
3 3
0 0 0
1 1 0
0 0 0

输出样例
4

（路径 (0,0)→(0,1)→(0,2)→(1,2)→(2,2)，4步）

考点：BFS 最短路模板。队列存坐标，入队即标记vis，用dist数组记录步数。这是 BFS 的招牌题，必须熟练。

AC第 4 题参考（迷宫最短路）▸

solution.cpp

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

const int N = 1005;
int n, m, g[N][N], dist[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];

    memset(dist, -1, sizeof(dist));   // -1表示未访问
    queue<pair<int,int>> q;
    q.push({0, 0});
    dist[0][0] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && g[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;   // 步数+1
                q.push({nx, ny});
            }
        }
    }
    cout << dist[n-1][m-1] << "\n";    // -1自动表示不可达
    return 0;
}

要点：用dist数组（-1=未访问）同时实现判重和记录步数，比按层写法更简洁。入队即更新dist（标记），防重复入队。dist[终点]即答案。

第 5 题：烂橘子（BFS —— 多源 BFS 变体，重要）

题意：n×m 网格，每个格子是 0（空）、1（新鲜橘子）、2（烂橘子）。每分钟，所有烂橘子会把上下左右相邻的新鲜橘子变烂。求让所有橘子都烂掉需要几分钟，如果有橘子永远烂不了输出 -1。

sample.txt

输入样例
3 3
2 1 1
1 1 0
0 1 1

输出样例
4

考点：多源 BFS（多个起点同时开始）。和单源 BFS 的区别——初始时把所有烂橘子一起入队（多个源头），然后一层层扩散。这是 BFS 的重要变体，能解决"多个起点同时扩散"的问题。

提示：① 先扫一遍，把所有初始烂橘子（值为2）全部入队，同时统计新鲜橘子数量；② 按层 BFS 扩散，每层时间+1，每感染一个新鲜橘子就计数；③ 最后判断是否所有新鲜橘子都被感染（没被感染说明不可达，输出-1）。

AC第 5 题参考（烂橘子/多源BFS）▸

solution.cpp

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

const int N = 1005;
int n, m, g[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;
    queue<pair<int,int>> q;
    int fresh = 0;                 // 新鲜橘子数
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 2) q.push({i, j});  // 所有烂橘子入队（多源！）
            if (g[i][j] == 1) fresh++;
        }

    int time = 0;
    while (!q.empty() && fresh > 0) {
        int sz = q.size();
        for (int s = 0; s < sz; s++) {   // 处理一整层
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 1) {
                    g[nx][ny] = 2;   // 变烂
                    fresh--;
                    q.push({nx, ny});
                }
            }
        }
        time++;                    // 一层=一分钟
    }
    cout << (fresh == 0 ? time : -1) << "\n";   // 还有新鲜的=不可达
    return 0;
}

要点：多源BFS——初始把所有烂橘子一起入队，它们同时向外扩散。按层统计时间。最后看是否还有新鲜橘子（有则-1）。多源BFS是处理"多起点同时扩散"的利器。

第 6 题：单词接龙最短变换（BFS —— 抽象状态，有难度）

题意：给两个长度相同的单词 begin 和 end，以及一个单词字典。每次只能改变一个字母，且改变后的单词必须在字典里。求从 begin 变到 end 的最少变换次数（包括起点和终点的变换链长度），无法变换输出 0。

sample.txt

输入样例
hit cog
5
hot dot dog lot log cog

输出样例
5

（hit→hot→dot→dog→cog，链长5）

考点：抽象状态的 BFS。这题的"图"不是网格——节点是单词，边是"只差一个字母"的关系。从 begin 开始 BFS，每次尝试改变每一位的每个字母，看是否在字典里。这题让你体会BFS 不只用于网格，任何"状态转移求最短"都能用 BFS。

提示：① 用 set 存字典方便查询；② 状态是当前单词，从 begin 出发；③ 转移：对当前单词的每一位，尝试换成 'a'~'z'，如果新单词在字典里且没访问过，入队；④ BFS 层数就是变换次数。这题偏难，想不出可以看答案理解"抽象状态 BFS"的思想。

参考答案，写完再看：

AC第 6 题参考（单词接龙）▸

solution.cpp

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

int main() {
    string begin, end;
    cin >> begin >> end;
    int k;
    cin >> k;
    set<string> dict;
    for (int i = 0; i < k; i++) {
        string s; cin >> s;
        dict.insert(s);
    }

    if (dict.find(end) == dict.end()) { cout << 0 << "\n"; return 0; }

    queue<string> q;
    map<string, int> dist;         // 到每个单词的变换链长度
    q.push(begin);
    dist[begin] = 1;               // 起点算1
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        if (cur == end) { cout << dist[cur] << "\n"; return 0; }
        // 尝试改变每一位
        for (int i = 0; i < cur.size(); i++) {
            string next = cur;
            for (char c = 'a'; c <= 'z'; c++) {
                next[i] = c;
                if (next != cur && dict.count(next) && !dist.count(next)) {
                    dist[next] = dist[cur] + 1;
                    q.push(next);
                }
            }
        }
    }
    cout << 0 << "\n";             // 无法变换
    return 0;
}

要点：抽象状态BFS——节点是单词，边是"差一个字母"。转移：对每一位尝试换'a'~'z'，新词在字典且没访问过就入队。用map当vis和dist。核心认知：BFS不限于网格，任何"状态转移求最短"都能用。 这题让你跳出"BFS=网格"的思维定式。

考点回顾与难度梯度：

岛屿数量——网格DFS模板
最大岛屿面积——DFS求连通块大小（返回值技巧）
被包围区域——DFS边界反向思维
迷宫最短路——BFS模板（dist写法）
烂橘子——多源BFS（多起点同时扩散）
单词接龙——抽象状态BFS（跳出网格思维）

最该吃透的认知：

第 1、4 题是 DFS/BFS 的标准模板，必须写到不假思索。
第 5 题多源 BFS 是个重要变体——"多个起点同时开始扩散"，烂橘子、多个火源蔓延、多个传送门等都是这个套路。
第 6 题打破"BFS只能用于网格"的误区——只要是"状态转移 + 求最短/最少"，就能用 BFS，状态可以是单词、数字、棋盘布局等任何东西。这个认知很重要。

教教练衔接coach

把代码贴给我，我重点帮你看：DFS/BFS选对没、vis判重对不对、第2题的返回值、第5题的多源入队、第6题的状态转移。

教教练衔接coach

或者你都过了，我们推进 2.2 回溯——DFS 的另一大应用，专门用来枚举所有方案（全排列、子集、组合），是暴力搜索和偷分（接 0.8）的核心武器。

第二部分 · 2.2

2.2 回溯

教教练衔接coach

进入 2.2 回溯。这是 DFS 的另一大应用方向——枚举所有可能的方案（全排列、子集、组合等）。回溯是"暴力搜索"的核心武器，也是 0.8 偷分策略里"小数据暴力"的主力。它的思想不难，但代码框架和那个"撤销"操作是关键，需要好好理解。

先抓住本质：

回溯 = 系统地枚举所有可能的方案，本质是带"撤销"的 DFS。
它"尝试一个选择 → 深入下去 → 撤销这个选择 → 尝试下一个选择"，把所有组合都试一遍。
关键动作：做选择 → 递归 → 撤销选择（这个"撤销"就是"回溯"得名的原因）。

一、理解回溯：决策树 + 撤销

核心图景

把所有方案的枚举过程想象成一棵决策树：

每个节点是一个"当前已经做的部分选择"。
每条分支是"下一步可以做的一个选择"。
叶子节点是一个"完整的方案"。

回溯就是 DFS 遍历这棵决策树，走到叶子收集一个方案，然后回退换分支。

为什么要"撤销"

DFS 走完一条分支后，要回退去走另一条分支。回退时，必须把这条分支做过的修改撤销掉，恢复到分叉前的状态，否则会影响其他分支。这个"撤销"是回溯的灵魂。

还记得 1.6 讲的递归"去时压栈、回时弹栈、自动还原局部变量"吗？回溯就是利用这个机制，在"回"的路上手动撤销我们对全局状态做的修改。

二、回溯的通用框架（背下来）

solution.cpp

void backtrack(当前状态, 已做的选择) {
    if (满足结束条件) {
        收集/记录答案;
        return;
    }
    for (每一个可能的选择) {
        if (这个选择不合法) continue;   // 剪枝（跳过非法选择）
        做出选择;                        // 修改状态
        backtrack(新状态, 更新后的选择);  // 递归深入
        撤销选择;                        // 关键！恢复状态（回溯）
    }
}

这个"做选择 → 递归 → 撤销选择"的三部曲是回溯的核心。下面用三个经典问题让你掌握它。

三、经典问题 1：全排列（最基础）

题意：给 n 个不同的数，输出它们的所有排列。比如 [1,2,3] 的排列有 123, 132, 213, 231, 312, 321 共 6 种（n! 个）。

思路：

一位一位地填。每个位置，尝试放还没用过的数。
用 used 数组标记哪些数已经用了。
填满 n 个位置就得到一个排列。

solution.cpp

int n;
int path[20];          // 当前正在构建的排列
bool used[20];         // 标记每个数是否已用
vector<vector<int>> ans;   // 存所有排列（也可以直接输出）

void backtrack(int pos) {  // pos = 当前要填第几个位置
    if (pos == n) {        // 填满了，得到一个完整排列
        // 输出 path[0..n-1]
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; i++) {     // 尝试每个数 1~n
        if (used[i]) continue;         // 这个数用过了，跳过
        path[pos] = i;                 // 做选择：第 pos 位填 i
        used[i] = true;                // 标记 i 已用
        backtrack(pos + 1);            // 递归填下一位
        used[i] = false;               // 撤销：恢复 i 未用（回溯）
    }
}

int main() {
    cin >> n;
    backtrack(0);      // 从第0位开始填
    return 0;
}

走一遍体会撤销的作用：

第0位填1，第1位填2，第2位填3 → 输出 1 2 3。
回退到第2位，撤销3（used[3]=false），没有别的数可填，回退到第1位。
撤销2（used[2]=false），第1位改填3，第2位填2 → 输出 1 3 2。
正是因为撤销了 used 标记，2 和 3 才能在后面的分支里重新被使用。 如果不撤销，后面就没数可用了。

全排列是回溯的"Hello World"，把"做选择 used[i]=true → 递归 → 撤销 used[i]=false"这个模式刻进脑子。

四、经典问题 2：子集（组合的基础）

题意：给 n 个数，输出所有子集（包括空集和全集）。比如 [1,2,3] 有 8 个子集：{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}（2ⁿ 个）。

思路：对每个数，有"选"或"不选"两种决策。枚举所有"选/不选"的组合就是所有子集。

solution.cpp

int n;
int a[20];
vector<int> path;      // 当前子集

void backtrack(int pos) {   // pos = 当前考虑第几个数
    if (pos == n) {         // 所有数都考虑完了
        // 输出当前子集 path
        cout << "{ ";
        for (int x : path) cout << x << " ";
        cout << "}\n";
        return;
    }
    // 决策1：不选 a[pos]
    backtrack(pos + 1);

    // 决策2：选 a[pos]
    path.push_back(a[pos]);    // 做选择
    backtrack(pos + 1);        // 递归
    path.pop_back();           // 撤销（回溯）
}

这里的撤销是 path.pop_back()——把刚加进去的数移除，恢复到"没选这个数"的状态，这样"不选"的分支才不受影响。

子集问题的框架是"每个元素选或不选"。这种"二选一"的决策树有 2ⁿ 个叶子。组合、子集和、能否凑出某个数等都基于这个框架。

五、经典问题 3：组合（从 n 个选 k 个）

题意：从 1~n 中选 k 个数的所有组合（不考虑顺序）。比如 n=4, k=2：{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}。

思路：和子集类似，但限定选 k 个，且为了避免重复（组合不看顺序，{1,2} 和 {2,1} 算一个），规定只能选比当前更大的数——用一个 start 参数控制起点。

solution.cpp

int n, k;
vector<int> path;

void backtrack(int start) {     // start = 从哪个数开始选（避免重复）
    if (path.size() == k) {     // 选够 k 个了
        for (int x : path) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int i = start; i <= n; i++) {   // 从 start 开始，保证递增
        path.push_back(i);      // 选 i
        backtrack(i + 1);       // 下一个从 i+1 开始（比 i 大）
        path.pop_back();        // 撤销
    }
}

int main() {
    cin >> n >> k;
    backtrack(1);   // 从1开始
    return 0;
}

关键是 start 参数：通过"下一个数从 i+1 开始"，保证选出的数严格递增，这样 {1,2} 会被枚举到，但 {2,1} 不会（因为选了2之后只能选3、4），自动去重。

组合 vs 排列的关键区别：排列要 used 标记（任意顺序，每个数能在任意位置），组合用 start 控制递增（固定顺序，避免重复）。这个区别很重要：看顺序用排列+used，不看顺序用组合+start。

六、剪枝：让回溯更快（重要优化）

回溯是指数级复杂度（n! 或 2ⁿ），数据稍大就慢。剪枝就是提前判断某个分支不可能产生答案，直接跳过，避免无用搜索。

剪枝的两种常见方式

① 可行性剪枝：当前选择已经违反约束，直接跳过（continue 或 return）。

② 最优性剪枝：当前方案已经不可能比已知最优解更好，停止这条分支。

例子：组合问题的剪枝

上面的组合问题，如果剩下的数不够凑齐 k 个，就没必要继续：

solution.cpp

void backtrack(int start) {
    if (path.size() == k) { /* 输出 */ return; }
    // 剪枝：剩余的数 (n - i + 1) 不足以补满 k 个，就停
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.push_back(i);
        backtrack(i + 1);
        path.pop_back();
    }
}

n - (k - path.size()) + 1 是 i 的上界——再往后剩的数就不够选满 k 个了。这个剪枝能大幅减少无效搜索。

剪枝是回溯的核心优化。一道回溯题能不能过，往往取决于剪枝。剪枝思想：在搜索过程中尽早发现"此路不通"，立刻回头，别浪费时间走到底才发现失败。N 皇后、数独这类题没有好的剪枝会超时。

七、经典问题 4：N 皇后（剪枝的经典应用，了解）

题意：在 n×n 棋盘上放 n 个皇后，使它们互不攻击（同行、同列、同对角线都算攻击）。求方案数。

思路：一行放一个皇后，枚举放在哪一列，用剪枝判断这列、对角线有没有冲突。

solution.cpp

int n, ans = 0;
bool col[20], diag1[40], diag2[40];   // 列、两个方向对角线是否被占

void backtrack(int row) {       // 第 row 行放皇后
    if (row == n) { ans++; return; }   // 所有行放完，方案+1
    for (int c = 0; c < n; c++) {       // 尝试每一列
        // 剪枝：这列或对角线被占，跳过
        if (col[c] || diag1[row+c] || diag2[row-c+n]) continue;
        col[c] = diag1[row+c] = diag2[row-c+n] = true;   // 做选择
        backtrack(row + 1);                               // 递归下一行
        col[c] = diag1[row+c] = diag2[row-c+n] = false;  // 撤销
    }
}

关键技巧：用 row+c 标记一条对角线、row-c+n 标记另一条对角线（同一对角线上 row+c 或 row-c 相同）。剪枝判断三个标记，冲突就跳过。

N 皇后是回溯 + 剪枝的经典题，体现了"枚举 + 约束检查 + 剪枝"的完整套路。铜牌阶段理解思路即可，不要求秒写。

八、回溯的识别信号与解题步骤

识别信号：题目要求"列出/输出所有..."、"有多少种方案"、"所有可能的组合/排列/路径"，且数据范围很小（n ≤ 20 左右，因为是指数复杂度）→ 回溯。

解题步骤：

确定"决策"是什么：每一步在做什么选择（填哪个数？选不选？放哪列？）。
确定结束条件：什么时候得到一个完整方案。
套框架：做选择 → 递归 → 撤销选择。
想剪枝：哪些分支可以提前判定失败，跳过。

结合 0.8 偷分：回溯是"暴力枚举"的主力。很多题正解是 DP 或贪心，但数据范围小时（n≤20），直接回溯暴力枚举所有方案就能 AC。这是 ICPC 赛制下"用暴力莽过数据弱的题"的关键手段（接 0.7 的复杂度反推：n≤10 用 O(n!)，n≤20 用 O(2ⁿ)）。

九、本节速记卡

回溯本质：带"撤销"的 DFS，枚举所有方案。核心三部曲：做选择 → 递归 → 撤销选择。
撤销是灵魂：回退时恢复状态（used[i]=false 或 path.pop_back()），否则影响其他分支。
三大经典：
全排列：used 标记 + 填每个位置（看顺序）
子集：每个元素选/不选（2ⁿ）
组合：start 参数控制递增（不看顺序，去重）
排列 vs 组合：看顺序用 used，不看顺序用 start。
剪枝：提前判断分支无效就跳过，是回溯能过的关键。
识别：「所有方案/排列/组合」+「小数据(n≤20)」→ 回溯。也是偷分暴力的主力。

回溯的精髓是"系统枚举 + 撤销"：通过决策树把所有可能性不重不漏地走一遍，靠"撤销"在分支间切换。理解了那个"做选择→递归→撤销"的节奏，回溯就通了。

和前面的联系：回溯 = DFS（2.1）+ 撤销 + 1.6 的递归思维。你会发现搜索的各种形态都是递归的变奏。

下一节 2.3 剪枝——其实这节已经带你入门了（组合剪枝、N皇后剪枝），下节会系统讲剪枝的各种策略，让暴力搜索快到能过。不过剪枝和回溯结合紧密，也可以先做题巩固回溯再深入剪枝。

教教练衔接coach

要不要我出一组回溯题（全排列、子集、组合、以及带剪枝的搜索）让你练熟这个核心框架？还是直接推进 2.3 剪枝？

配套练习题

好，给你 6 道回溯题，三大经典框架（排列/子集/组合）打底，再加带约束和剪枝的变体。回溯的关键是把"做选择→递归→撤销"的节奏练成本能，以及理解排列/组合的区别。

老规矩：先自己写，重点体会"撤销"的作用、想清楚"看不看顺序（用 used 还是 start）",再展开对照。

第 1 题：全排列（回溯 —— 最基础模板）

题意：给一个整数 n，输出 1~n 的所有排列，按字典序输出。

sample.txt

考点：回溯最基础模板。used 数组 + 逐位填数。体会"选择 used[i]=true → 递归 → 撤销 used[i]=false"。

AC第 1 题参考（全排列）▸

solution.cpp

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

int n;
int path[20];
bool used[20];

void backtrack(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++) cout << path[i] << " \n"[i == n-1];
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        path[pos] = i;
        used[i] = true;
        backtrack(pos + 1);
        used[i] = false;        // 撤销
    }
}

int main() {
    cin >> n;
    backtrack(0);
    return 0;
}

要点：used 标记 + 逐位填。" \n"[i==n-1] 是个小技巧：最后一个元素后输出换行，其余输出空格。撤销 used[i]=false 让数字能在其他分支复用。从1到n顺序枚举，自然得到字典序。

第 2 题：所有子集（回溯 —— 选/不选框架）

题意：给 n 个不同的整数，输出所有子集。每个子集占一行，元素按输入顺序，空集输出空行。

sample.txt

输入样例
3
1 2 3

输出样例
（空行）
3
2
2 3
1
1 3
1 2
1 2 3

（输出顺序取决于实现，只要是全部8个子集即可）

考点：子集的"每个元素选或不选"框架。撤销是 path.pop_back()。

AC第 2 题参考（所有子集）▸

solution.cpp

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

int n;
vector<int> a, path;

void backtrack(int pos) {
    if (pos == n) {
        for (int i = 0; i < path.size(); i++)
            cout << path[i] << " \n"[i == (int)path.size()-1];
        if (path.empty()) cout << "\n";   // 空集输出空行
        return;
    }
    backtrack(pos + 1);            // 不选 a[pos]
    path.push_back(a[pos]);        // 选 a[pos]
    backtrack(pos + 1);
    path.pop_back();               // 撤销
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    backtrack(0);
    return 0;
}

要点：每个元素"不选"和"选"两条分支。撤销是 pop_back。先递归"不选"再"选"会影响输出顺序，但所有子集都会被枚举到。

第 3 题：组合（回溯 —— start 控制递增）

题意：从 1~n 中选出 k 个数的所有组合，按字典序输出。

sample.txt

输入样例
4 2

输出样例
1 2
1 3
1 4
2 3
2 4
3 4

考点：组合用 start 参数保证递增、自动去重（不看顺序）。对比第1题：排列用 used（看顺序），组合用 start（不看顺序）。这个区别要彻底分清。

AC第 3 题参考（组合）▸

solution.cpp

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

int n, k;
vector<int> path;

void backtrack(int start) {
    if (path.size() == k) {
        for (int i = 0; i < k; i++) cout << path[i] << " \n"[i == k-1];
        return;
    }
    for (int i = start; i <= n; i++) {
        path.push_back(i);
        backtrack(i + 1);          // 下一个从 i+1 开始（递增，去重）
        path.pop_back();           // 撤销
    }
}

int main() {
    cin >> n >> k;
    backtrack(1);
    return 0;
}

要点：start 参数是组合的关键——backtrack(i+1) 保证选出的数严格递增，避免 {1,2} 和 {2,1} 重复。和第1题对比：排列任意位置任意数（used），组合只能递增选（start）。

第 4 题：括号生成（回溯 —— 带约束的构造，重要）

题意：给 n 对括号，生成所有合法的括号组合。

sample.txt

输入样例
3

输出样例
((()))
(()())
(())()
()(())
()()()

考点：带约束的回溯。每一步可以放 ( 或 )，但要满足约束：① 左括号数不超过 n；② 右括号数不超过左括号数（否则不合法）。练习"在回溯中加入合法性约束"——这其实就是剪枝的雏形。

提示：递归参数记录已用的左括号数 open 和右括号数 close。能放 ( 的条件是 open < n；能放 ) 的条件是 close < open。当 open == close == n 时得到一个完整方案。

AC第 4 题参考（括号生成）▸

solution.cpp

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

int n;
string path;

void backtrack(int open, int close) {  // 已用的左、右括号数
    if (open == n && close == n) {     // 都用完 n 个
        cout << path << "\n";
        return;
    }
    if (open < n) {                    // 还能放左括号
        path.push_back('(');
        backtrack(open + 1, close);
        path.pop_back();               // 撤销
    }
    if (close < open) {                // 右括号数 < 左括号数才能放右
        path.push_back(')');
        backtrack(open, close + 1);
        path.pop_back();               // 撤销
    }
}

int main() {
    cin >> n;
    backtrack(0, 0);
    return 0;
}

要点：两个约束条件 open < n（左括号没用完）和 close < open（保证合法）就是剪枝——只生成合法的，不合法的分支根本不进入。这种"用约束过滤分支"是回溯+剪枝的核心思想。

第 5 题：电话号码字母组合（回溯 —— 多选择映射）

题意：给一个数字字符串（2-9），每个数字对应几个字母（像手机九宫格：2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz）。输出所有可能的字母组合。

sample.txt

输入样例
23

输出样例
ad ae af bd be bf cd ce cf

（2对应abc，3对应def，每位各取一个字母的所有组合）

考点：回溯处理"每一位有多个选择"。逐位处理数字，每位尝试它对应的所有字母。练习"决策不是选不选，而是从多个选项里选一个"。

提示：用一个映射存每个数字对应的字母串。回溯第 pos 位时，遍历 digits[pos] 对应的所有字母，每个字母接到 path 后递归下一位，pos 到末尾时收集答案。

AC第 5 题参考（电话号码字母组合）▸

solution.cpp

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

string digits;
string path;
string mp[10] = {"", "", "abc", "def", "ghi", "jkl",
                 "mno", "pqrs", "tuv", "wxyz"};  // 数字→字母映射

void backtrack(int pos) {
    if (pos == digits.size()) {
        cout << path << " ";
        return;
    }
    int d = digits[pos] - '0';         // 当前数字
    for (char c : mp[d]) {             // 遍历它对应的所有字母
        path.push_back(c);
        backtrack(pos + 1);
        path.pop_back();               // 撤销
    }
}

int main() {
    cin >> digits;
    backtrack(0);
    cout << "\n";
    return 0;
}

要点：每位的"决策"是从该数字对应的字母里选一个。用 mp[10] 存映射。digits[pos]-'0' 把字符转数字（接 0.2/string 章节的字符技巧）。逐位深入，到末尾收集。

第 6 题：N 皇后（回溯 + 剪枝 —— 经典综合，有难度）

题意：在 n×n 棋盘上放 n 个皇后，使它们互不攻击（同行、同列、同对角线不能有两个皇后）。求总共有多少种放法。

sample.txt

输入样例
4

输出样例
2

（4皇后有2种解）

考点：回溯 + 剪枝的经典题。逐行放皇后，每行枚举列，用标记数组判断列和两条对角线是否冲突（剪枝）。对角线的标记技巧：row+col 标记一个方向、row-col+n 标记另一个方向。

提示：① 一行放一个皇后（保证不同行）；② 枚举列 c，检查 col[c]、diag1[row+c]、diag2[row-c+n] 是否被占；③ 没冲突则放下（三个标记置true）、递归下一行、撤销（置false）；④ 放满 n 行方案数+1。这题综合了回溯框架 + 剪枝 + 对角线技巧，想不出可看答案。

参考答案，写完再看：

AC第 6 题参考（N 皇后）▸

solution.cpp

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

int n, ans = 0;
bool col[20], diag1[40], diag2[40];   // 列、主对角线、副对角线

void backtrack(int row) {
    if (row == n) { ans++; return; }   // 放满n行，方案+1
    for (int c = 0; c < n; c++) {
        // 剪枝：列或对角线冲突就跳过
        if (col[c] || diag1[row + c] || diag2[row - c + n]) continue;
        col[c] = diag1[row + c] = diag2[row - c + n] = true;   // 放皇后
        backtrack(row + 1);                                    // 下一行
        col[c] = diag1[row + c] = diag2[row - c + n] = false;  // 撤销
    }
}

int main() {
    cin >> n;
    backtrack(0);
    cout << ans << "\n";
    return 0;
}

要点：① 逐行放（自动不同行）；② 对角线技巧——同一主对角线 row+c 相同，同一副对角线 row-c 相同（加n防负数下标）；③ 三个标记数组做剪枝，冲突直接跳过；④ 标准的"放下→递归→撤销"。这题是回溯+剪枝的集大成，把它写顺了，回溯就掌握了。

考点回顾与难度梯度：

全排列——回溯基础（used，看顺序）
所有子集——选/不选框架（2ⁿ）
组合——start 控制递增（不看顺序）
括号生成——带约束的回溯（剪枝雏形）
电话号码——多选择映射
N 皇后——回溯 + 剪枝 + 对角线技巧

最该吃透的对应关系（回溯的核心分类）：

问题类型	关键技巧	看顺序吗
排列	used 标记	看（每个位置任意数）
组合/子集	start 参数 / 选不选	不看（保证递增去重）

第1题和第3题的对比是重点——同样是枚举，排列用 used、组合用 start，区别在于"看不看顺序"。这个分清了，回溯题就不会用错框架。

另外第4、6题展示了回溯的进阶——在搜索中加入约束/剪枝，只走合法分支。这是从"纯暴力枚举"到"带约束搜索"的过渡，正好引出下一节剪枝。

教教练衔接coach

把代码贴给我，我重点帮你看：撤销写对没、排列/组合框架用对没、第4题的约束条件、第6题的对角线标记。

教教练衔接coach

或者你都过了，我们推进 2.3 剪枝——系统讲各种剪枝策略，让指数级的暴力搜索快到能过题。其实第4、6题你已经尝到剪枝的甜头了，下节会讲得更系统。

第二部分 · 2.3

2.3 剪枝

教教练衔接coach

进入 2.3 剪枝。你在 2.2 已经尝到剪枝的甜头了（括号生成的约束、N 皇后的冲突判断）。这一节系统讲剪枝策略——它是让指数级暴力搜索快到能 AC 的关键技术。同样的搜索，会剪枝和不会剪枝，可能是 AC 和 TLE 的差别。

先抓住本质：

剪枝 = 在搜索过程中，提前识别出"这条路绝不可能产生（更优）答案"，立刻砍掉，不再深入。
搜索树是指数级的，剪枝就是砍掉搜索树上没用的枝丫，大幅减少实际搜索量。

剪掉的枝越多、越早，搜索越快。剪枝不改变答案的正确性，只是跳过注定无用的分支。

一、为什么需要剪枝

回溯/DFS 的复杂度是指数级（n!、2ⁿ）。比如 n=15 的全排列是 15! ≈ 1.3万亿，纯暴力必然 TLE。但很多分支其实走几步就能看出不可能成功，没必要走到底。剪枝就是在这些分支刚露出"必败"苗头时就掐掉，把实际搜索量降到可接受范围。

一个形象的比喻：你在迷宫里找出口，走到某条路发现前面是死胡同的尽头，聪明的做法是立刻掉头，而不是把死胡同里每个角落都摸一遍。剪枝就是"及时掉头"。

二、剪枝的两大类型（核心）

类型 1：可行性剪枝（最常用）

判断当前状态是否还有可能满足约束。如果当前的部分选择已经违反了约束，或者即使后面做得再好也无法满足要求，立刻剪掉。

例子（你见过的）：

括号生成：右括号数不能超过左括号数，超了就剪（2.2 第4题）。
N 皇后：这一列/对角线已经有皇后了，剪掉（2.2 第6题）。
组合问题：剩下的数不够凑满 k 个，剪掉（2.2 正文的组合剪枝）。

通用形式：

solution.cpp

if (当前选择违反约束) continue;        // 跳过这个选择
if (剩余资源不足以达成目标) return;     // 整个分支剪掉

类型 2：最优性剪枝（求最优解时用）

当求"最优解"时，如果当前方案已经不可能比已知最优解更好，剪掉。

核心：维护一个"当前最优答案" best。搜索中，如果当前已经付出的代价 ≥ best（再继续只会更差），或者当前代价 + 乐观估计的剩余最小代价 ≥ best（再怎么乐观也超不过最优），就剪掉。

通用形式：

solution.cpp

if (当前已用代价 >= best) return;              // 已经不可能更优
if (当前代价 + 剩余最乐观估计 >= best) return;  // 加上最好情况也不够好

最优性剪枝常用于"求最小代价/最少步数/最优方案"的搜索题。关键是设计一个乐观估计（理论上剩余部分最少还要花多少），用它提前判断"这条路注定超过当前最优"。

三、几种实用的剪枝技巧

技巧 1：约束检查前置（最基本）

在做选择之前就检查这个选择合不合法，不合法直接跳过，别等做完才发现。这是最基本的剪枝，2.2 的题都用了。

solution.cpp

for (每个选择) {
    if (这个选择不合法) continue;   // 提前过滤，不进入递归
    做选择; 递归; 撤销;
}

技巧 2：排序 + 剪枝（很常用）

先把数据排序，让"更可能失败/成功"的情况先被发现，配合剪枝效果更好。

经典例子：搜索"能否从一堆数里选若干个凑成目标和"。如果从大到小排序，大的数先尝试，更快接近目标或更快发现超了；如果当前数加上去就超过目标，后面更大的也不用试了（配合下一个技巧）。

技巧 3：可行性预判（剩余量剪枝）

预先算出"剩余的最大可能贡献"，如果连这都不够达成目标，直接剪。

例子：凑数问题，如果"当前和 + 剩余所有数之和 < 目标"，那无论怎么选都凑不到，剪掉。

solution.cpp

if (curSum + remainSum < target) return;   // 剩下全选也不够，剪

技巧 4：去重剪枝（避免重复方案）

当数据有重复元素时，避免生成重复的方案。做法：排序后，同一层跳过相同的元素。

solution.cpp

sort(a.begin(), a.end());
for (int i = start; i < n; i++) {
    if (i > start && a[i] == a[i-1]) continue;  // 同层去重：跳过重复
    做选择; 递归(i+1); 撤销;
}

i > start && a[i] == a[i-1] 的意思是：在同一层（同一个 start 下），如果当前元素和前一个相同，就跳过——因为前一个已经枚举过这种选择了，再选会产生重复方案。这是处理"含重复元素的组合/子集"的标准剪枝。

技巧 5：记忆化（避免重复子问题）

如果搜索中同一个状态会被多次访问，把算过的结果存下来，下次直接用。这就是记忆化搜索——重要到下一节（2.4）专门讲，它是通往动态规划的桥梁。

四、一个完整例子：子集和问题（综合剪枝）

题意：给 n 个正整数和目标 target，问能否选出若干个数，使它们的和恰好等于 target。

纯暴力：每个数选或不选，2ⁿ 枚举。n 大就 TLE。

加剪枝：

solution.cpp

int n, target;
int a[30];
bool found = false;

void dfs(int pos, int curSum, int remainSum) {
    // remainSum = 从 pos 到末尾还没考虑的数之和
    if (found) return;                    // 已找到答案，所有分支都剪掉
    if (curSum == target) { found = true; return; }   // 找到
    if (pos == n) return;                 // 没数了

    // 剪枝1（可行性）：当前和已超过目标，剪（前提：都是正数）
    if (curSum > target) return;
    // 剪枝2（可行性）：当前和 + 剩余全部 < 目标，再选也不够，剪
    if (curSum + remainSum < target) return;

    // 选 a[pos]
    dfs(pos + 1, curSum + a[pos], remainSum - a[pos]);
    // 不选 a[pos]
    dfs(pos + 1, curSum, remainSum - a[pos]);
}

剪枝效果：

剪枝1（curSum > target）：和超了就没必要继续（正数只会越加越大）。
剪枝2（curSum + remainSum < target）：剩下全选都不够，必败，剪。
found 标志：找到一个解后，立刻让所有分支返回，不再搜索。

这三个剪枝能把很多分支提前砍掉，让原本会 TLE 的暴力变得可行。这就是剪枝的威力——不改变算法本质，但让它快到能用。

五、剪枝的思考方法（怎么想到剪枝）

遇到搜索 TLE，按这个思路找剪枝点：

当前分支会不会违反约束？ → 可行性剪枝（违反就剪）。
当前分支还有没有可能达成目标？ → 估计剩余量，不够就剪。
求最优解时，当前分支还有没有可能超过已知最优？ → 最优性剪枝。
会不会有重复方案/重复状态？ → 去重剪枝 / 记忆化。
排序能不能让剪枝更早触发？ → 排序 + 剪枝。

剪枝的核心思维：在搜索的每一步都问一句"这条路还有戏吗？"——没戏就立刻回头。问得越早、越准，剪得越多，搜索越快。

六、剪枝的注意事项

剪枝必须保证正确性：只能剪掉"确实不可能产生（更优）答案"的分支，不能误剪可能有答案的分支，否则会漏解 WA。剪枝条件要想清楚再写。
剪枝有成本：每次剪枝判断本身也要花时间。如果剪枝条件很复杂但剪不掉多少分支，可能得不偿失。好的剪枝是"判断简单 + 砍掉大量分支"。
剪枝顺序：把最容易触发、最能砍分支的剪枝放前面，能更快返回。

七、本节速记卡

剪枝本质：提前砍掉"不可能产生（更优）答案"的搜索分支，让指数暴力变可行。不改变正确性。
两大类型：
可行性剪枝：违反约束 / 剩余量不够达成目标 → 剪。（最常用）
最优性剪枝：当前代价已 ≥ 已知最优 → 剪。（求最优解时）
实用技巧：约束前置、排序+剪枝、剩余量预判、去重剪枝（同层跳重复）、记忆化。
思考方法：每一步问"这条路还有戏吗"，没戏就回头。
注意：剪枝不能误剪（保正确）；好剪枝=判断简单+砍得多。

剪枝是搜索的"加速器"。它的精髓是用判断换搜索——花一点点判断的代价，省下大量无用搜索。一道搜索题能不能在时限内过，常常就取决于剪枝设计得好不好。

和前面的联系：剪枝是回溯（2.2）的优化，去重剪枝呼应了组合的去重思想，而记忆化剪枝直接引出下一节——

下一节 2.4 记忆化搜索，是一个特别重要的承上启下：它用"把算过的结果存下来"解决搜索中的重复子问题，既是剪枝的一种（避免重复状态），又是动态规划（第三部分）的思维入口。还记得 1.6 那个朴素斐波那契重复计算 O(2ⁿ) 的痛点吗？记忆化就是它的解药。学完记忆化，你就摸到 DP 的门了。

教教练衔接coach

要不要我出几道带剪枝的搜索题巩固一下？还是直接推进 2.4 记忆化搜索——这是搜索通往 DP 的关键一步，强烈建议趁热打铁？

配套练习题

好，给你 5 道带剪枝的搜索题，重点练可行性剪枝、去重剪枝、最优性剪枝。这些题不剪枝大概率 TLE，剪了才能过，正好让你体会剪枝的威力。

老规矩：先自己写，重点想清楚"哪里能剪、剪的条件对不对（别误剪）",再展开对照。

第 1 题：子集和判定（可行性剪枝 —— 入门）

题意：给 n 个正整数和目标 target，判断能否选出若干个数，使和恰好等于 target。能输出 YES，否则 NO。（n ≤ 30）

sample.txt

输入样例
5 11
2 3 5 7 1

输出样例
YES

（选 3+7+1=11，或 2+3+5+1=11）

考点：选/不选的搜索 + 可行性剪枝。三个剪枝：①和超过target就剪（正数）②找到答案就停 ③（可选）剩余量不够就剪。不剪枝 2³⁰ 会 TLE。

提示：dfs(pos, curSum)，剪枝 if (curSum > target) return;，找到 curSum == target 置标志返回。

AC第 1 题参考（子集和判定）▸

solution.cpp

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

int n, target;
int a[35];
long long suf[35];   // 后缀和：suf[i]=a[i]+...+a[n-1]
bool found = false;

void dfs(int pos, int curSum) {
    if (found) return;                       // 已找到，剪
    if (curSum == target) { found = true; return; }
    if (pos == n) return;
    if (curSum > target) return;             // 剪枝1：超了（正数）
    if (curSum + suf[pos] < target) return;  // 剪枝2：剩余全选也不够

    dfs(pos + 1, curSum + a[pos]);   // 选
    dfs(pos + 1, curSum);            // 不选
}

int main() {
    cin >> n >> target;
    for (int i = 0; i < n; i++) cin >> a[i];
    suf[n] = 0;
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i+1] + a[i];  // 算后缀和
    dfs(0, 0);
    cout << (found ? "YES" : "NO") << "\n";
    return 0;
}

要点：三个剪枝缺一不可——超了剪、不够剪、找到停。后缀和 suf 用于"剩余量预判"剪枝。这些剪枝把 2³⁰ 砍到能过。

第 2 题：组合总和（去重 + 可行性剪枝 —— 有重复元素）

题意：给一个可能有重复数字的数组 candidates 和目标 target，找出所有不重复的组合，使组合中的数字和为 target。每个数字在每个组合中只能用一次。

sample.txt

输入样例
4 8
10 1 2 7 6 1 5

（candidates = [10,1,2,7,6,1,5]，target=8）

sample.txt

（所有和为8的不重复组合）

考点：去重剪枝——数组有重复元素（两个1），要避免生成重复组合。标准做法：排序后，同一层跳过相同元素（i > start && a[i]==a[i-1] 时 continue）。再加可行性剪枝（和超了就停）。

提示：① 先排序；② 用 start 控制（组合，不看顺序）；③ 关键去重 if (i > start && cand[i] == cand[i-1]) continue;；④ 排序后 cand[i] > target-curSum 时直接 break（后面更大，都不用试了）。

AC第 2 题参考（组合总和/去重）▸

solution.cpp

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

int n, target;
vector<int> cand, path;

void dfs(int start, int curSum) {
    if (curSum == target) {
        for (int i = 0; i < path.size(); i++)
            cout << path[i] << " \n"[i == (int)path.size()-1];
        return;
    }
    for (int i = start; i < n; i++) {
        if (i > start && cand[i] == cand[i-1]) continue;  // 去重剪枝：同层跳重复
        if (curSum + cand[i] > target) break;             // 排序后，超了就break（后面更大）
        path.push_back(cand[i]);
        dfs(i + 1, curSum + cand[i]);   // i+1：每个数只用一次
        path.pop_back();
    }
}

int main() {
    cin >> n >> target;
    cand.resize(n);
    for (int i = 0; i < n; i++) cin >> cand[i];
    sort(cand.begin(), cand.end());     // 排序是去重和break剪枝的前提
    dfs(0, 0);
    return 0;
}

要点：① 去重剪枝 i > start && cand[i]==cand[i-1]——同一层若当前数和前一个相同就跳过（前一个已枚举过这种选择）；② 排序后用 break 而非 continue（后面的更大，必然也超）；③ dfs(i+1) 保证每个数只用一次。去重剪枝是处理重复元素的标准手段。

第 3 题：分割成相等子集（可行性剪枝 + 排序优化 —— 略难）

题意：给一个正整数数组，判断能否把它分成两个和相等的子集。能输出 YES，否则 NO。

sample.txt

输入样例
4
1 5 11 5

输出样例
YES

（{1,5,5} 和 {11}，两边和都是11）

sample.txt

输入样例
3
1 2 5

输出样例
NO

（总和8，无法分成两个和为4的子集）

考点：转化——分成两个和相等的子集，等价于"能否选出若干个数，和为总和的一半"。所以先判断总和是否为偶数（奇数直接NO），再转成第1题的"子集和判定"（target = 总和/2）。加上从大到小排序能让剪枝更快触发。

提示：① 求总和，奇数直接NO；② target = sum/2；③ 降序排序（大数先试，更快触发剪枝）；④ 套子集和判定 + 剪枝。

AC第 3 题参考（分割相等子集）▸

solution.cpp

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

int n, target;
int a[105];
long long suf[105];
bool found = false;

void dfs(int pos, int curSum) {
    if (found) return;
    if (curSum == target) { found = true; return; }
    if (pos == n) return;
    if (curSum > target) return;
    if (curSum + suf[pos] < target) return;

    dfs(pos + 1, curSum + a[pos]);
    dfs(pos + 1, curSum);
}

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
    if (sum % 2 != 0) { cout << "NO\n"; return 0; }   // 奇数无法平分
    target = sum / 2;
    sort(a, a + n, greater<int>());      // 降序，大数先试，剪枝更快
    suf[n] = 0;
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i+1] + a[i];
    dfs(0, 0);
    cout << (found ? "YES" : "NO") << "\n";
    return 0;
}

要点：① 转化——平分等于"选出和为 sum/2 的子集"；② 奇数和直接NO（重要特判）；③ 降序排序让大数先尝试，更快触发"超了"剪枝；④ 复用第1题的子集和判定框架。这题考的是"转化 + 剪枝"。

第 4 题：最少硬币数搜索（最优性剪枝 —— 重要）

题意：给几种面值的硬币（每种无限个）和目标金额 amount，求凑出 amount 的最少硬币数，凑不出输出 -1。（用搜索+剪枝做，不用DP）

sample.txt

输入样例
3 11
1 2 5

输出样例
3

（5+5+1=11，3枚）

考点：最优性剪枝。维护当前最优解 best，搜索中如果"已用硬币数 ≥ best"就剪（不可能更优）。配合面值从大到小排序（先用大面值，更快接近目标，更快得到一个较优的 best 来剪枝）。

提示：① 面值降序排序；② dfs(剩余金额, 已用硬币数)；③ 最优性剪枝 if (coinCount >= best) return;；④ 凑成时更新 best = min(best, coinCount)；⑤ 进阶剪枝：用当前最大面值估计"剩余金额至少还需几枚"，不够好就剪。

注意：这题正解其实是DP（接1.5凑硬币），这里用搜索+剪枝是为了练最优性剪枝。实际比赛该用DP，但剪枝思想要会。

AC第 4 题参考（最少硬币/最优性剪枝）▸

solution.cpp

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

int n, amount;
vector<int> coins;
int best;

void dfs(int idx, int remain, int count) {
    if (remain == 0) { best = min(best, count); return; }
    if (idx == n) return;
    if (count >= best) return;          // 最优性剪枝：已不可能更优
    // 进阶剪枝：用当前面值estimate最少还需几枚，加上还≥best就剪
    if (count + (remain + coins[idx] - 1) / coins[idx] >= best) return;

    // 从用最多个当前面值开始尝试（贪心式，更快找到好解）
    for (int k = remain / coins[idx]; k >= 0; k--) {
        dfs(idx + 1, remain - k * coins[idx], count + k);
    }
}

int main() {
    cin >> n >> amount;
    coins.resize(n);
    for (int i = 0; i < n; i++) cin >> coins[i];
    sort(coins.rbegin(), coins.rend());  // 降序：大面值先
    best = 1e9;
    dfs(0, amount, 0);
    cout << (best == (int)1e9 ? -1 : best) << "\n";
    return 0;
}

要点：① 最优性剪枝 count >= best——已用硬币数不少于当前最优，剪；② 进阶剪枝用"剩余金额÷当前最大面值"估计下界；③ 降序排序 + 优先用大面值，更快得到一个好的 best 用于剪枝。这是最优性剪枝的典型，理解"用已知最优剪掉劣解"。 （注：实战这题用DP更好，这里练剪枝思想。）

第 5 题：单词方块拼图（可行性剪枝 —— 综合，有难度）

题意：给一个 n×m 字符网格和一个单词 word，判断能否在网格中找到这个单词——从某个格子出发，每次移动到上下左右相邻格子（同一个格子不能重复使用），路径上的字母依次拼成 word。能输出 YES，否则 NO。

sample.txt

输入样例
3 4
ABCE
SFCS
ADEE
ABCCED

输出样例
YES

（A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D(2,1)，拼成ABCCED）

考点：网格 DFS + 可行性剪枝。从每个格子尝试 DFS 匹配 word。剪枝：①当前格子字母不等于 word 对应位就立刻返回（最重要的剪枝）②用 vis 标记避免重复使用格子（走过的撤销，因为不同起点要重新搜）。这是搜索剪枝在网格上的应用。

提示：① 枚举每个格子作起点；② dfs(x, y, idx) 表示当前在(x,y)要匹配 word[idx]；③ 剪枝 if (g[x][y] != word[idx]) return false;；④ idx 到 word 末尾说明匹配成功；⑤ 标记当前格子 vis，递归四个方向，撤销 vis（回溯，因为换个起点要能重新用这个格子）。

参考答案，写完再看：

AC第 5 题参考（单词搜索）▸

solution.cpp

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

int n, m;
char g[105][105];
string word;
bool vis[105][105];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

bool dfs(int x, int y, int idx) {
    if (g[x][y] != word[idx]) return false;   // 剪枝：字母不匹配，立刻返回
    if (idx == word.size() - 1) return true;  // 匹配到最后一个字母，成功

    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
            if (dfs(nx, ny, idx + 1)) {
                vis[x][y] = false;   // 撤销（虽然成功了，习惯性恢复）
                return true;
            }
        }
    }
    vis[x][y] = false;        // 撤销：换起点时这个格子要能重新用
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> g[i][j];
    cin >> word;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (dfs(i, j, 0)) {       // 每个格子作起点试
                cout << "YES\n";
                return 0;
            }
    cout << "NO\n";
    return 0;
}

要点：① 关键剪枝 g[x][y] != word[idx] 字母不匹配立刻返回（避免无用深入）；② vis 标记防止同一路径重复用格子；③ 撤销 vis（回溯）——因为不同起点的搜索要能重新使用这个格子，这是网格回溯的关键。把搜索剪枝和回溯结合的好例子。

考点回顾：

子集和判定——可行性剪枝（超了剪、不够剪、找到停）
组合总和——去重剪枝（同层跳重复）+ break剪枝
分割相等子集——转化 + 剪枝（奇数特判 + 降序优化）
最少硬币——最优性剪枝（用已知最优剪劣解）
单词搜索——网格剪枝（不匹配立即返回）+ 回溯

三种剪枝都练到了：

可行性剪枝（第1、5题）：违反约束/不可能达成就剪——最常用。
去重剪枝（第2题）：同层跳过重复元素——处理重复数据的标准手段。
最优性剪枝（第4题）：当前已不如已知最优就剪——求最优解必备。

最该吃透的：

第2题的去重剪枝 i > start && a[i]==a[i-1]——这个套路在很多"含重复元素求组合"的题里反复出现，记死。
第4题的最优性剪枝——"维护 best，劣于 best 就剪"是求最优解搜索的通用加速法。

一个重要提醒：剪枝条件一定要想清楚会不会误剪。比如第1题"curSum > target 就剪"只在全是正数时成立，如果有负数这个剪枝就错了（负数能把和拉回来）。剪枝的前提条件要牢记。

教教练衔接coach

把代码贴给我，我重点帮你看：剪枝条件对不对、有没有误剪风险、去重剪枝写对没、第5题的vis撤销。

教教练衔接coach

或者你都过了，我们推进 2.4 记忆化搜索——这是搜索通往动态规划的关键桥梁，用"存住算过的结果"消除重复计算。还记得1.6那个朴素斐波那契O(2ⁿ)的痛点吗？记忆化就是解药，学完它你就摸到DP的门了。强烈建议趁热打铁！

第二部分 · 2.4

2.4 记忆化搜索

教教练衔接coach

进入 2.4 记忆化搜索。这是整个课程的一个关键转折点——它是搜索通往动态规划的桥梁。学完这节，你就摸到 DP 的门了。我会特意从 1.6 那个斐波那契的痛点讲起，让你看清"搜索"是怎么自然演化成"DP"的。

先用一句话点破本质：

记忆化搜索 = 普通递归搜索 + "把算过的结果存下来，下次直接用"。
它解决的核心问题是：搜索中同一个子问题被重复计算很多次。把每个子问题的答案算一次、存起来，重复遇到时直接查表，避免重算。

一、从斐波那契看清"重复计算"这个病（关键引入）

还记得 1.6 那个朴素斐波那契吗？

solution.cpp

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);   // 看起来很简洁
}

它的问题是疯狂重复计算。我们把 fib(5) 的递归展开看看：

sample.txt

                    fib(5)
              /              \
          fib(4)            fib(3)
         /     \           /     \
     fib(3)   fib(2)   fib(2)   fib(1)
     /   \     /   \    /   \
  fib(2) fib(1) ...  ...

注意看：fib(3) 被算了 2 次，fib(2) 被算了 3 次，fib(1) 更多……n 越大，重复越恐怖。每个 fib(k) 都会衍生出一整棵重复的子树，所以复杂度是指数级 O(2ⁿ)，n=50 就慢到没法用。

病根：fib(3) 算出来是 2，但程序不"记得"，每次遇到都重新算一遍整棵子树。

二、记忆化：给递归装上"记忆"

解药很简单：用一个数组 memo 把算过的结果存下来，每次先查表，算过了就直接返回，没算过才计算并存表。

solution.cpp

int memo[100];      // 存储已算出的结果，初始化为 -1（表示"还没算过"）

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];   // 查表：算过了直接返回（核心！）
    memo[n] = fib(n-1) + fib(n-2);       // 没算过：算出来并存表
    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(memo));      // 初始化 -1
    cout << fib(50) << "\n";             // 瞬间出结果
    return 0;
}

就加了两行（查表 + 存表），复杂度从 O(2ⁿ) 暴降到 O(n)！因为每个 fib(k) 只会真正计算一次，之后都是查表 O(1)。

对比那棵树：现在 fib(3) 第一次算完存进 memo，第二次遇到直接查表返回 2，整棵重复子树被砍掉了。这其实就是 2.3 讲的"避免重复状态"剪枝的极致形式。

记忆化的三要素（套路化）：
1. 一个 memo 数组：存每个子问题的答案。
2. 初始化为"未计算"标志：通常 -1（或其他不可能是答案的值）。
3. 递归里：先查表（算过就返回），后计算（算完存表）。
这三步是记忆化的固定模板，套到任何重复子问题的搜索上都管用。

三、记忆化搜索的标准框架

solution.cpp

int memo[N];   // 维度取决于"状态由几个变量决定"

int solve(状态参数) {
    if (到达边界) return 边界值;              // 递归出口
    if (memo[状态] != 未计算标志)
        return memo[状态];                   // 查表
    int res = 通过子问题计算当前问题;          // 递归计算
    memo[状态] = res;                        // 存表
    return res;
}

关键是想清楚"状态"：一个子问题由哪几个变量唯一确定？这几个变量就是 memo 的维度（下标）。状态设计对了，记忆化就成功了一大半——而这个"状态"，正是动态规划里的核心概念。

四、例题：数字三角形（记忆化经典，直通 DP）

题意：一个数字三角形，从顶部走到底部，每步只能走到下方相邻的左或右，求路径上数字之和的最大值。

sample.txt

        7
      3   8
    8   1   0
  2   7   4   4
最大路径: 7→3→8→7 = 25

朴素递归思路：定义 solve(i, j) = 从位置 (i,j) 走到底部能获得的最大和。

solution.cpp

int solve(int i, int j) {
    if (i == n - 1) return a[i][j];   // 到最后一行，就是它自己
    // 往左下走 or 往右下走，取较大的，加上当前值
    return a[i][j] + max(solve(i+1, j), solve(i+1, j+1));
}

问题：和斐波那契一样，solve(i,j) 会被重复计算（中间的位置会被上面多个位置访问到）。加记忆化：

solution.cpp

int n;
int a[105][105];
int memo[105][105];

int solve(int i, int j) {
    if (i == n - 1) return a[i][j];           // 出口
    if (memo[i][j] != -1) return memo[i][j];  // 查表
    memo[i][j] = a[i][j] + max(solve(i+1, j), solve(i+1, j+1));  // 算+存
    return memo[i][j];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    memset(memo, -1, sizeof(memo));
    cout << solve(0, 0) << "\n";   // 从顶点开始
    return 0;
}

这里的"状态"是 (i, j)——位置由行和列两个变量决定，所以 memo 是二维的。每个 (i,j) 只算一次，复杂度从指数级降到 O(n²)。

划重点：这道"数字三角形"是记忆化搜索和动态规划的同一道题。你现在用记忆化（自顶向下递归 + memo）解决了它；到第三部分，你会用 DP（自底向上递推）再解一遍。它们求的是同一个东西，只是方向相反。 这就是为什么说记忆化是 DP 的入口。

五、记忆化搜索 vs 动态规划（核心认知，必须理解）

这是本节最重要的认知。记忆化搜索和动态规划本质是同一件事，只是实现方向不同：

	记忆化搜索	动态规划（DP）
方向	自顶向下（从大问题递归到小问题）	自底向上（从小问题递推到大问题）
实现	递归 + memo 数组	循环 + dp 数组
思路	"我要解决大问题，需要先解决哪些小问题"（递归求）	"我先把所有小问题解决，再组合出大问题"（循环推）
本质	完全一样：都是把每个子问题算一次、存起来、避免重复

它们的核心都是：

状态：子问题由什么变量唯一确定（记忆化的递归参数 = DP 的 dp 数组下标）。
转移：当前问题怎么由子问题得到（记忆化的递归式 = DP 的递推式）。
存储：把子问题答案存起来复用（memo 数组 = dp 数组）。

关键领悟：学会了记忆化搜索，你已经在做动态规划了，只是换了个方向。 很多人觉得 DP 难、想不出递推式，但如果先用记忆化"自顶向下"地想"大问题需要哪些小问题"，往往更自然、更好想。记忆化是理解 DP 最友好的入口。

六、记忆化搜索的优势（什么时候用它而非 DP）

虽然记忆化和 DP 等价，但记忆化有时更好写、更好想：

思路更直觉：直接按"大问题 → 小问题"递归，不用想"按什么顺序递推"。DP 要保证算 dp[i] 时它依赖的子问题都算好了（递推顺序），记忆化不用操心顺序——递归自然处理。
只算用到的状态：DP 通常把所有状态都算一遍，记忆化只计算真正会被访问到的状态。如果很多状态用不到，记忆化更省。
状态转移复杂时更清晰：当转移关系绕、维度多时，递归写法往往比循环更直观。

什么时候用 DP 而非记忆化：

递归深度太大可能栈溢出（接 1.6），DP 用循环没这问题。
需要极致的常数优化（DP 循环通常比递归快一点）。
状态转移顺序很清晰、所有状态都要算时，DP 更自然。

实战建议：想不出 DP 递推式时，先写记忆化搜索——按"大问题需要哪些小问题"递归，加上 memo，往往一下就通了。记忆化是你解 DP 题的"备用方案"和"思维拐杖"。

七、记忆化搜索解题步骤

定义状态：用递归函数 solve(参数) 表示一个子问题，想清楚参数（状态）是什么。
写递归关系：当前问题怎么由更小的子问题组合得到（信仰之跃，接 1.6）。
确定边界：递归出口（最小的子问题直接返回）。
加记忆化：开 memo 数组，先查表后计算，算完存表。
初始化 + 调用：memo 初始化为未计算标志，从初始状态调用。

八、本节速记卡

记忆化本质：递归搜索 + memo 存结果，消除重复子问题计算。指数级 → 多项式级。
三要素：①memo 数组 ②初始化未计算标志(-1) ③先查表后计算、算完存表。
状态是核心：子问题由哪几个变量决定 = memo 的维度 = DP 的下标。
记忆化 = DP：自顶向下(递归+memo) vs 自底向上(循环+dp)，本质完全相同，方向相反。
优势：思路直觉、只算用到的状态、转移复杂时更清晰。
实战：想不出 DP 递推式，先写记忆化——这是解 DP 题的思维拐杖。

🌉 这一节是真正的承上启下。回头看，你从 1.6 的递归出发，经过 2.1-2.3 的搜索和剪枝，现在到了记忆化——搜索的终点，恰好是 DP 的起点。那个困扰朴素递归的"重复计算"痛点，被 memo 一举解决，而这个解决方案，本身就是动态规划的灵魂。

你现在站在一个重要的门槛上：第二部分（搜索）即将结束，第三部分（动态规划，铜牌的重中之重）即将开启。而记忆化搜索让这个过渡变得无缝——DP 不是一个全新的东西，而是你已经会的记忆化搜索换个方向写。

🎉 第二部分：搜索基本完成！ 我们走过了 DFS/BFS、回溯、剪枝、记忆化搜索。（2.5 双向BFS/IDA* 是拓展内容，铜牌阶段可暂时跳过。）

接下来就是 第三部分：动态规划——铜牌的核心中的核心，也是最需要多做题培养"DP 思维"的部分。有了记忆化的基础，你会发现 DP 没那么可怕。

教教练衔接coach

要不要我出几道记忆化搜索的题（巩固"状态定义 + memo"，并体会它和 DP 的关系）？还是直接开启 第三部分 3.1 DP 思维——趁着记忆化的热乎劲，无缝进入动态规划？

教教练衔接coach

我强烈建议先做几道记忆化的题，因为它直接决定你 DP 学得顺不顺。你定。

配套练习题

好，给你 5 道记忆化搜索题。重点练"定义状态 + 写递归式 + 加 memo"这套流程，并刻意让你体会"这其实就是 DP"。这几道题之后都会在第三部分用 DP 重做，现在先用记忆化"自顶向下"地解决它们。

老规矩：先自己写，重点想清楚"状态是什么（memo 几维、下标是啥）、递归式怎么写",再展开对照。

第 1 题：数字三角形（记忆化经典 —— 直通 DP）

题意：数字三角形，从顶走到底，每步走向下方相邻的左或右，求路径数字和的最大值。

sample.txt

输入样例
4
7
3 8
8 1 0
2 7 4 4

输出样例
25

（7→3→8→7=25）

考点：记忆化入门。状态 (i,j) = 从(i,j)走到底的最大和。递归式 solve(i,j) = a[i][j] + max(solve(i+1,j), solve(i+1,j+1))。memo 二维。

AC第 1 题参考（数字三角形）▸

solution.cpp

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

int n, a[105][105], memo[105][105];

int solve(int i, int j) {
    if (i == n - 1) return a[i][j];           // 出口：最后一行
    if (memo[i][j] != -1) return memo[i][j];  // 查表
    memo[i][j] = a[i][j] + max(solve(i+1, j), solve(i+1, j+1));  // 算+存
    return memo[i][j];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    memset(memo, -1, sizeof(memo));
    cout << solve(0, 0) << "\n";
    return 0;
}

要点：状态(i,j)，递归式取左右下较大者加当前值。memo二维。这就是记忆化的标准模板。

第 2 题：不同路径数（记忆化 —— 计数型）

题意：一个 m×n 的网格，机器人从左上角 (0,0) 走到右下角 (m-1,n-1)，每次只能向右或向下走一步。求有多少条不同的路径。

sample.txt

输入样例
3 4

输出样例
10

（3行4列的网格，从左上到右下共10条路径）

考点：记忆化求方案数。状态 (i,j) = 从(i,j)到终点的路径数。递归式 solve(i,j) = solve(i+1,j) + solve(i,j+1)（向下的路径数 + 向右的路径数）。边界：到达终点返回1，越界返回0。体会"计数型"递归——把子问题的方案数相加。

提示：出口——i==m-1 && j==n-1 返回1（到终点算1条路径）；越界返回0。方案数可能大，注意类型（这题数据小用int够，但要有溢出意识）。

AC第 2 题参考（不同路径数）▸

solution.cpp

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

int m, n;
long long memo[105][105];

long long solve(int i, int j) {
    if (i == m - 1 && j == n - 1) return 1;   // 到终点：1条路径
    if (i >= m || j >= n) return 0;           // 越界：0条
    if (memo[i][j] != -1) return memo[i][j];
    memo[i][j] = solve(i+1, j) + solve(i, j+1);  // 下 + 右
    return memo[i][j];
}

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

要点：计数型递归——方案数 = 各子问题方案数之和（下面的路径数 + 右边的路径数）。出口到终点返回1。用 long long（路径数可能大）。

第 3 题：最长递增子序列长度（记忆化 —— 重要模型）

题意：给一个数组，求最长严格递增子序列（LIS）的长度。子序列不要求连续，但要保持原顺序且严格递增。

sample.txt

输入样例
6
1 3 2 4 3 5

输出样例
4

（最长递增子序列如 1 3 4 5 或 1 2 4 5 或 1 2 3 5，长度4）

考点：经典 LIS 模型。状态 solve(i) = 以第 i 个元素结尾的最长递增子序列长度。递归式：solve(i) = 1 + max(solve(j))，其中 j < i 且 a[j] < a[i]（从所有能接在 i 前面的 j 转移）。答案是所有 solve(i) 的最大值。这是 DP 最经典的模型之一，必须掌握。

提示：① solve(i) 枚举所有 j < i，如果 a[j] < a[i]，可以接在 j 后面，取 solve(j)+1 的最大值；② 如果前面没有更小的，solve(i)=1（自己单独成序列）；③ 最终答案遍历所有 i 取 max。这题 O(n²)，记忆化和 DP 写法都要会。

AC第 3 题参考（最长递增子序列）▸

solution.cpp

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

int n, a[1005], memo[1005];

int solve(int i) {       // 以 a[i] 结尾的 LIS 长度
    if (memo[i] != -1) return memo[i];
    int res = 1;         // 至少自己一个
    for (int j = 0; j < i; j++)
        if (a[j] < a[i])              // a[j] 能接在 a[i] 前面
            res = max(res, solve(j) + 1);
    memo[i] = res;
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    memset(memo, -1, sizeof(memo));
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, solve(i));  // 所有结尾取max
    cout << ans << "\n";
    return 0;
}

要点：① 状态"以 i 结尾"是 LIS 的经典定义；② 枚举所有更小的前驱 j，取 solve(j)+1 最大；③ 答案是所有 solve(i) 的最大值（LIS 可能以任意位置结尾），不是 solve(n-1)。这是 LIS 必须掌握的标准解法。

第 4 题：硬币凑数方案（记忆化 —— 完全背包雏形）

题意：给几种面值的硬币（每种无限个）和目标金额 amount，求凑出 amount 的最少硬币数，凑不出返回 -1。

sample.txt

输入样例
3 11
1 2 5

输出样例
3

（5+5+1=11，3枚）

考点：记忆化解凑硬币（接 1.5 那个贪心会错的题，这次用记忆化正确求解）。状态 solve(amount) = 凑出 amount 的最少硬币数。递归式 solve(amount) = 1 + min(solve(amount - coin))，枚举每种硬币。边界：solve(0)=0。这是完全背包的雏形，第三部分会专门讲。

提示：① solve(x) 枚举每种硬币 coin，如果 x >= coin，可以用一枚 coin，剩下凑 x-coin，即 solve(x-coin)+1，取最小；② 出口 solve(0)=0；③ 凑不出用一个大值（如1e9）表示，最后判断；④ memo 一维，下标是金额。

AC第 4 题参考（硬币凑数）▸

solution.cpp

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

int amount, n;
vector<int> coins;
int memo[10005];

int solve(int x) {       // 凑出 x 的最少硬币数
    if (x == 0) return 0;           // 出口：凑0需0枚
    if (memo[x] != -1) return memo[x];
    int res = 1e9;
    for (int coin : coins)
        if (x >= coin)
            res = min(res, solve(x - coin) + 1);  // 用一枚coin
    memo[x] = res;
    return res;
}

int main() {
    cin >> n >> amount;
    coins.resize(n);
    for (int i = 0; i < n; i++) cin >> coins[i];
    memset(memo, -1, sizeof(memo));
    int ans = solve(amount);
    cout << (ans >= 1e9 ? -1 : ans) << "\n";
    return 0;
}

要点：① 状态是"金额 x"，一维 memo；② 枚举每种硬币，solve(x-coin)+1 取最小；③ 凑不出用大值1e9，最后判断输出-1。这就是完全背包思想——每种硬币可无限用。 对比1.5贪心会错，记忆化/DP保证正确。

第 5 题：最长公共子序列长度（记忆化 —— 双序列 DP，有难度）

题意：给两个字符串 s1 和 s2，求它们的最长公共子序列（LCS）的长度。公共子序列指在两个串中都按顺序出现（不要求连续）的字符序列。

sample.txt

输入样例
abcde
ace

输出样例
3

（"ace" 是公共子序列，长度3）

考点：经典 LCS 模型，双序列记忆化。状态 solve(i,j) = s1 前 i 个字符和 s2 前 j 个字符的 LCS 长度。递归式：

如果 s1[i-1] == s2[j-1]（当前字符相同）：solve(i,j) = solve(i-1,j-1) + 1
否则：solve(i,j) = max(solve(i-1,j), solve(i,j-1))

memo 二维。这是双序列 DP 的代表，状态是"两个序列各处理到哪"，很重要。 想不出可看答案理解。

提示：① 状态 (i,j) 表示 s1 用前 i 个、s2 用前 j 个；② 末尾字符相同→匹配上，两边都退一格 +1；③ 不同→要么放弃 s1 末尾、要么放弃 s2 末尾，取较大；④ 边界 solve(0,j)=solve(i,0)=0（任一串为空，LCS为0）。

参考答案，写完再看：

AC第 5 题参考（最长公共子序列）▸

solution.cpp

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

string s1, s2;
int memo[1005][1005];

int solve(int i, int j) {    // s1前i个、s2前j个的LCS长度
    if (i == 0 || j == 0) return 0;          // 出口：任一为空，LCS=0
    if (memo[i][j] != -1) return memo[i][j];
    int res;
    if (s1[i-1] == s2[j-1])                  // 末尾字符相同
        res = solve(i-1, j-1) + 1;           // 匹配上，两边退一格+1
    else                                      // 不同
        res = max(solve(i-1, j), solve(i, j-1));  // 放弃一边的末尾
    memo[i][j] = res;
    return res;
}

int main() {
    cin >> s1 >> s2;
    memset(memo, -1, sizeof(memo));
    cout << solve(s1.size(), s2.size()) << "\n";
    return 0;
}

要点：① 双序列状态 (i,j)——分别表示两个串处理到哪；② 字符相同→solve(i-1,j-1)+1（这对字符匹配进LCS）；③ 不同→max(放弃s1末尾, 放弃s2末尾)；④ 边界任一串空则LCS为0。注意 s1[i-1] 因为 i 表示"前 i 个"，下标要减1。 LCS是双序列DP的代表，务必理解状态设计。

考点回顾与它们对应的 DP 模型：

数字三角形——记忆化入门 → 线性DP
不同路径——计数型递归 → 路径DP
最长递增子序列(LIS)——→ 经典线性DP
硬币凑数——→ 完全背包
最长公共子序列(LCS)——→ 双序列DP

这 5 道题覆盖了 DP 的几大经典模型，你现在用记忆化"自顶向下"解决了它们。第三部分会用 DP"自底向上"重做，到时你会清楚看到：同一道题，记忆化和 DP 求的是一回事，只是方向相反。

最该吃透的认知：

每道题的核心都是"状态定义"——solve(i,j) 到底代表什么子问题。状态想对了，递归式自然就出来了。这个"定义状态"的能力，就是 DP 的核心能力。
第3题 LIS（"以 i 结尾"）和第5题 LCS（"两序列各到哪"）是两个极其重要的状态设计范式，后面 DP 反复用，现在先建立印象。

一个重要观察：你会发现写记忆化时，根本没有"DP 的恐惧感"——就是普通递归 + memo，很自然。这正是我让你先学记忆化的目的：等进入 DP，你会发现它不过是把这些递归"反过来用循环写"，没有新东西。

教教练衔接coach

把代码贴给我，我重点帮你看：状态定义对不对、递归式对不对、memo 维度对不对、第3题答案取所有结尾max、第5题的下标减1。

教教练衔接coach

或者你都过了，我们就正式开启 第三部分：动态规划！从 3.1 DP 思维 开始——我会带你看清 DP 和记忆化的关系，把"DP 三要素"讲透，让你彻底跨过 DP 这道坎。这是铜牌的核心，但有了记忆化的基础，你已经成功了一半。准备好就出发！