1一个统一的视角同一个问题① 状态 当前局面是什么 ② 转移 从当前局面能走到哪些局面 ③ 目标 什么算「找到答案」 ④ 走法 深度优先递归还是广度优先队列五种形态只是这四个答案不同。形态状态走法问什么回溯已经做过的选择路径深度优先有多少种方案 / 列出方案BFS图上的节点广度优先队列最少几步DFS 连通块网格上的格子深度优先能不能到达记忆化搜索局面 缓存深度优先同 DFS但同一局面只算一次拓扑排序图上的节点 入度广度优先队列依赖顺序 / 判环2回溯2.1核心思想每一步做一个决定走到头记录答案然后退回来换一个决定。画面是一棵决策树。以 LC 78 子集nums [1,2,3]为例[] ┌───────────┴───────────┐ 选1 不选1 [1] [] ┌───┴───┐ ┌───┴───┐ 选2 不选2 选2 不选2 [1,2] [1] [2] []回溯 深度优先地走这棵树回来时把选择撤销。2.2理论三段式四个变体void backtrack(路径, 选择列表) { if (结束条件) { 记录答案; return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 新的选择列表); 撤销选择; // ★ 回溯的灵魂 } }四个变体区别只在「选择列表怎么写」变体选择列表代表题选 / 不选二元分支要 / 不要LC 78 子集排列顺序有关used[]只能选没用过的LC 46 全排列组合顺序无关start下标只能选后面的LC 39 / 40 组合总和二维网格四方向 标记访问LC 79 单词搜索2.3 LC例题2.3.1 LC78子集—— 选 / 不选class Solution { public: vectorvectorint ret; vectorint path; void dfs(vectorint nums, int i) { if (i (int)nums.size()) { // 出口所有元素都决定完了 ret.push_back(path); return; } // ① 不选 nums[i] dfs(nums, i 1); // ② 选 nums[i] path.push_back(nums[i]); dfs(nums, i 1); path.pop_back(); // ★ 撤销 } vectorvectorint subsets(vectorint nums) { ret.clear(); // ★ 成员容器入口复位 path.clear(); dfs(nums, 0); return ret; } };这一题的另一个写法「枚举mask从 0 到 2n-1」的位掩码解法代码更短、无递归。 两者复杂度一样但位掩码只适合纯枚举一旦加去重 / 剪枝 / 额外条件就只能用回溯。位掩码版见另一篇《位运算从一个整数到一个集合》。2.3.2 LC46全排列—— 引入used[]class Solution { public: vectorvectorint ret; vectorint path; vectorbool visit; void dfs(vectorint nums) { if (path.size() nums.size()) { // 出口凑齐一个排列 ret.push_back(path); return; } for (int i 0; i (int)nums.size(); i) { if (visit[i]) continue; // 用过的跳过 visit[i] true; // 做选择两个状态 path.push_back(nums[i]); dfs(nums); path.pop_back(); // 撤销两个状态 visit[i] false; } } vectorvectorint permute(vectorint nums) { ret.clear(); visit.assign(nums.size(), false); // ★ assign 而非 resize dfs(nums); return ret; } };要点path和visit是两个都要撤销的状态。2.3.4 LC39组合综合——start下标class Solution { public: vectorvectorint ret; vectorint path; void dfs(vectorint candidates, int start, int remain) { if (remain 0) { // 出口刚好凑够 ret.push_back(path); return; } for (int i start; i (int)candidates.size(); i) { if (candidates[i] remain) break; // 依赖升序的剪枝 path.push_back(candidates[i]); dfs(candidates, i, remain - candidates[i]); // ★ 传 i本数可再用 path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { ret.clear(); sort(candidates.begin(), candidates.end()); // ★ break 剪枝的前提 dfs(candidates, 0, target); return ret; } };start传i还是i1可重复使用 → 传 i 下一个位置还能再选自己 不可重复用 → 传 i 1 下一个位置只能往后选剪枝的前提必须先排序if (candidates[i] remain) break;这个break依赖数组升序—— 一旦当前数超标后面的更大全都不用试。实测candidates[8,7,4,3], target11漏 sort 版本输出 0 个正确是 3 个。2.4 常见错误回溯#错误后果1pop_back()漏了路径越来越长答案全错2只撤销path忘了used/ 标记数组后面的分支被错误挡住3组合题start传错ivsi1可重复 / 不可重复搞反4去重写成i 0 a[i] a[i-1]把同枝的合法情况也去掉了应为i start5排列题不用used用start生成的是组合而不是排列6N 皇后对角线下标r-c为负数组越界要n偏移3BFS3.1 核心思想队列里放「同一层的所有局面」一层扩完再扩下一层。为什么 BFS 能求最短路先访问的一定步数更少层序保证。3.2理论两个模板单源 BFSqueueState q; q.push(start); visited[start] true; // ★ 入队时就标记 while (!q.empty()) { auto cur q.front(); q.pop(); for (next : cur 的所有转移) { if (合法 !visited[next]) { visited[next] true; // ★ 入队时就标记 dist[next] dist[cur] 1; q.push(next); } } }多源 BFS差别只在开局for (每个源点) { q.push(源点); dist[源点] 0; } // ★ 所有源点一起入队3.3LC题目——LC994腐烂的橘子网格里 0 空格1 新鲜2 腐烂。每分钟每个腐烂橘子让上下左右的新鲜橘子腐烂。 求全部腐烂的最少分钟数有烂不到的返回 -1。class Solution { int dx[4] {0, 0, -1, 1}; int dy[4] {-1, 1, 0, 0}; public: int orangesRotting(vectorvectorint grid) { int n grid.size(), m grid[0].size(); queuepairint,int q; // ① 多源所有腐烂橘子一起入队 for (int i 0; i n; i) for (int j 0; j m; j) if (grid[i][j] 2) q.push(make_pair(i, j)); int ret 0; while (q.size()) { int size q.size(); // ★ 先取本层大小 bool flag false; // ★ 本层真扩散了才 1 while (size--) { int x q.front().first, y q.front().second; q.pop(); for (int a 0; a 4; a) { int i x dx[a], j y dy[a]; if (i 0 i n j 0 j m grid[i][j] 1) { grid[i][j] 2; // ★ 原地标记入队前 q.push(make_pair(i, j)); flag true; } } } if (flag) ret; // 第 0 层初始腐烂不算时间 } // ② 收尾还有新鲜橘子 → 烂不到 for (auto e : grid) for (auto ee : e) if (ee 1) return -1; return ret; } };两个实测踩过的坑①ret要「本层真扩散才 1」否则第 0 层初始腐烂橘子也被算成 1 分钟。 实测[[2,1,1],[1,1,0],[0,1,1]]应 4无条件ret会得 5。② 队列是push不是push_back那是 vector 的接口。3.4 常见错误BFS#错误后果1「出队时才标记」而不是「入队时标记」同一个点被多次入队 → 超时 / 答案错2多源 BFS 只把第一个源点入队结果变成「到某一个源点」的距离3层序忘了先取q.size()内外层混在一起无法按层计时4网格越界判断写在访问数组之后越界读 → 崩溃4DFS4.1核心思想从一个格子出发能走到的所有格子是一块。用 DFS 或 BFS 都行。最关键的一个认知什么时候要撤销什么时候不用这个格子以后还要不要留给「另一条路」用结论依赖「怎么走到这里」→ 撤销LC 79 单词搜索结论只依赖「状态本身」→ 永久标记LC 200 岛屿数量4.2模板void dfs(int i, int j) { if (越界 || 已访问 || 不是目标) return; visited[i][j] true; dfs(i1, j); dfs(i-1, j); dfs(i, j1); dfs(i, j-1); }4.3 例LC 200 岛屿数量class Solution { int n, m; vectorvectorbool use; int dx[4] {0, 0, -1, 1}; int dy[4] {-1, 1, 0, 0}; public: int numIslands(vectorvectorchar grid) { n grid.size(), m grid[0].size(); int ret 0; use.assign(n, vectorbool(m, false)); // ★ assign 而非 resize for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 use[i][j] false) { use[i][j] true; // ★ 先标记再递归 ret; dfs(grid, i, j); } } } return ret; } void dfs(vectorvectorchar grid, int i, int j) { for (int a 0; a 4; a) { int x i dx[a], y j dy[a]; if (x 0 x n y 0 y m use[x][y] false grid[x][y] 1) { use[x][y] true; dfs(grid, x, y); // 无撤销行 —— 本题的核心 } } } };4.4 常见错误连通块#错误后果1LC 733 图像渲染起点颜色相同没特判无限递归2外层计数时「先递归后标记」同一块岛里重复计数3大网格1000×1000用递归 DFS栈溢出 → 改 BFS 或手写栈5记忆化搜索5.1 核心思想同一个局面答案唯一→ 算过一次就存起来下次直接取。普通 DFS 每次从头算 O(指数级) 记忆化搜索 每个状态只算一次 O(状态数)这是「能过 100%」和「只能过小数据」的分界线。5.2 什么时候可以记忆化判据同一状态答案是否唯一LC 79 单词搜索memo[i][j]的答案还取决于「已经走过哪些格子」visit 集合 → 状态描述不完整 →不能记忆化LC 329f(i,j)只取决于(i,j)自己与「怎么走到这儿的」无关 → 状态唯一 →可以记忆化5.3 模板 状态设计的四种形态int dfs(状态) { if (memo[状态] 已算过) return memo[状态]; // ① 查表 if (终止) return 边界值; int res 0; for (转移) res 合并(res, dfs(下一状态)); // ② 递归 return memo[状态] res; // ③ 存表 }状态形态例子坐标LC 329 矩阵最长递增路径坐标 某个维度LC 576 出界路径数剩余步数区间[l, r]LC 486 预测赢家位掩码LC 464 我能赢吗5.4 例LC 329 矩阵中的最长递增路径class Solution { int dx[4] {0, 0, -1, 1}; int dy[4] {-1, 1, 0, 0}; int n, m; vectorvectorint memo; public: int longestIncreasingPath(vectorvectorint matrix) { n matrix.size(), m matrix[0].size(); memo.assign(n, vectorint(m, -1)); // ★ -1 没算过 int ret 0; for (int i 0; i n; i) for (int j 0; j m; j) ret max(ret, dfs(matrix, i, j)); return ret; } int dfs(vectorvectorint matrix, int i, int j) { if (memo[i][j] ! -1) return memo[i][j]; // ① 查表 int flag 1; // 兜底走不动了长度 1含自己 for (int a 0; a 4; a) { int x i dx[a], y j dy[a]; if (x 0 x n y 0 y m matrix[x][y] matrix[i][j]) { flag max(flag, dfs(matrix, x, y) 1); } } return memo[i][j] flag; // ③ 存表 } };本题为什么不需要visit数组「只能往值更大的格子走」这个约束天然保证不会绕圈 不可能 A B 又 B A→ 图是有向无环图DFS 一定终止。5.5 常见错误记忆化#错误后果1memo用 0 当「没算过」分不清「答案 0」和「没算过」2状态少了维度漏剩余步数 / 区间端点答案错3类内成员没在入口复位resize多测时读到上一轮残留4记忆化的 key 用「完整路径」而不是「状态」永不重复等于没记忆化6拓扑排序6.1核心思想DAG 上只走「入度为 0」的点没有前置依赖的点。普通 BFS所有起点入队 拓扑 BFS所有【入度为 0】的点入队 出队后 把它指向的点的入度 -1减到 0 就入队6.2例LC207课程表prerequisites[i] [a, b]表示「想修 a必须先修 b」。判断能否修完 —— 等价于判环。class Solution { public: bool canFinish(int n, vectorvectorint p) { // p[1] - p[0]需要学完 p[1]才能学 p[0] vectorint in(n, 0); vectorvectorint out(n); // out[b] { 所有以 b 为先修课的课 } for (auto e : p) { in[e[0]]; // a 多了一个先修课 out[e[1]].push_back(e[0]); // b 的后继清单里加上 a } queueint q; for (int i 0; i n; i) if (in[i] 0) q.push(i); // ★ 所有入度 0 入队多源 while (q.size()) { int size q.size(); while (size--) { int cur q.front(); q.pop(); for (int i 0; i (int)out[cur].size(); i) { if (--in[out[cur][i]] 0) q.push(out[cur][i]); // ★ 减到 0 才入队 } } } for (auto e : in) if (e ! 0) return false; // 还有课没被解锁 → 有环 return true; } };6.3 常见错误拓扑#错误后果1建图方向反了[a,b]是 b→a判环能过但输出顺序全错2用「队列是否为空」判环应该用「出队个数 n」3入度数组从邻接表读邻接表存的是出边入度必须单独统计7横向对比回溯BFSDFS 连通记忆化拓扑走法深度优先广度优先深度优先深度优先广度优先载体决策树状态图网格状态 DAG依赖图记什么路径距离是否访问局面答案入度问什么所有方案最少步能否到达最优 / 计数依赖顺序关键动作撤销入队标记四方向查表存表入度减到 0复杂度指数剪枝后降低O(状态数)O(格子数)O(状态数)O(VE)五种写法都是「给状态、找转移、定目标」这三步。区别只在走法深 / 广 记什么路径 / 距离 / 访问 / 答案 / 入度。