DFS 模板总结：关键是“这一层到底在选择什么？”

DFS 模板总结：关键是“这一层到底在选择什么？”

DFS 最核心的思想不是死记代码，而是先想清楚：

“这一层我到底在决定什么？”

只要这个问题想明白，DFS 通常就知道该怎么写了。

一、DFS 通用模板

voiddfs(当前状态){// 1. 递归出口if(到达终点){记录答案;return;}// 2. 枚举当前这一层的所有选择for(所有可能的选择){// 3. 判断这个选择是否合法if(合法){// 4. 做选择修改状态;// 5. 进入下一层dfs(下一个状态);// 6. 回溯：撤销选择恢复状态;}}}

可以直接记成：

枚举选择 ↓ 判断是否合法 ↓ 做选择 ↓ 递归 ↓ 撤销选择（回溯）

二、不同 DFS 题，“选择”是不一样的

这是最重要的部分。

以后看到 DFS，先问自己一句：

“这一层我到底在决定什么？”

三、全排列 DFS

1. 这一层在选择什么？

假设要求：

1 2 3

的所有排列。

当：

step=1;

表示：

现在要决定第 1 个位置放哪个数字。

可以选择：

1 2 3

所以：

全排列中，每一层是在选择“当前位置放哪个数字”。

2. 模板

intn;inta[10];boolvis[10];voiddfs(intstep){// 递归出口if(step>n){for(inti=1;i<=n;i++)cout<<a[i]<<" ";cout<<"\n";return;}// 枚举当前这个位置可以放哪个数字for(inti=1;i<=n;i++){if(!vis[i]){// 做选择a[step]=i;vis[i]=true;// 进入下一层dfs(step+1);// 回溯vis[i]=false;}}}

3. 这一题怎么理解“做选择”？

a[step]=i;vis[i]=true;

表示：

第step个位置选择数字i。

然后：

dfs(step+1);

表示：

当前这一位已经确定，继续决定下一位。

递归回来以后：

vis[i]=false;

表示：

撤销刚才的选择，让数字i可以被其他排列继续使用。

4. 一句话记忆

全排列：每一层决定“这个位置放谁”。

四、迷宫 DFS

1. 这一层在选择什么？

当前站在：

(x, y)

下一步通常有四种可能：

上 下 左 右

所以：

迷宫 DFS 每一层是在选择“下一步往哪个方向走”。

2. 方向数组

intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};

分别表示：

上 下 左 右

3. 模板

voiddfs(intx,inty){// 到达终点if(x==tx&&y==ty){ans++;return;}// 枚举四个方向for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];// 越界if(nx<1||nx>n||ny<1||ny>m)continue;// 是障碍物if(mp[nx][ny]==1)continue;// 已经走过if(vis[nx][ny])continue;// 做选择vis[nx][ny]=true;// 递归dfs(nx,ny);// 回溯vis[nx][ny]=false;}}

4. 这一题怎么理解“做选择”？

vis[nx][ny]=true;

表示：

我决定下一步走到(nx, ny)。

然后：

dfs(nx,ny);

表示：

已经走到了新位置，继续考虑下一步。

回来以后：

vis[nx][ny]=false;

表示：

这条路线搜索完了，把这个位置恢复成“没有访问过”。

5. 一句话记忆

迷宫：每一层决定“下一步往哪里走”。

五、八皇后 DFS

1. 这一层在选择什么？

八皇后一般是一行一行放。

例如：

dfs(row);

表示：

当前正在决定第row行的皇后放在哪里。

这一行可以枚举：

第 1 列 第 2 列 第 3 列 ... 第 n 列

所以：

八皇后每一层是在选择“当前这一行放在哪一列”。

2. 模板

voiddfs(introw){// 所有行都放完if(row>n){ans++;return;}// 枚举当前这一行的每一列for(intcol=1;col<=n;col++){if(这一列和两个对角线都没有皇后){// 做选择标记这一列;标记两个对角线;// 进入下一行dfs(row+1);// 回溯取消这一列标记;取消两个对角线标记;}}}

3. 核心过程

当前第 row 行 ↓ 枚举 col ↓ 判断第 col 列能不能放 ↓ 可以 ↓ 放皇后 ↓ dfs(row + 1) ↓ 拿走皇后

4. 一句话记忆

八皇后：每一层决定“这一行皇后放在哪一列”。

六、组合 DFS

例如：

从 1、2、3、4 中选择 2 个数

可能得到：

1 2 1 3 1 4 2 3 2 4 3 4

1. 这一层在选择什么？

每一层是在决定：

下一个加入组合的是哪个数字。

2. 模板

vector<int>path;voiddfs(intstart){// 已经选够 k 个数if(path.size()==k){// 输出答案return;}// 从 start 开始枚举for(inti=start;i<=n;i++){// 做选择path.push_back(i);// 下一层从 i + 1 开始dfs(i+1);// 回溯path.pop_back();}}

3. 这一题怎么理解“做选择”？

path.push_back(i);

表示：

把数字i放进当前组合。

然后：

dfs(i+1);

表示：

下一层从i+1往后继续选。

回来以后：

path.pop_back();

表示：

撤销刚才加入的数字，尝试其他选择。

4. 一句话记忆

组合：每一层决定“下一个选哪个数”。

七、子集 DFS

例如集合：

{1, 2, 3}

对于每一个元素，都有两种选择：

选 不选

所以：

子集问题每一层是在决定“当前元素选还是不选”。

1. 模板

vector<int>path;voiddfs(intindex){// 所有元素都考虑完if(index==n){// 输出当前子集return;}// 情况1：选择 nums[index]path.push_back(nums[index]);dfs(index+1);// 回溯path.pop_back();// 情况2：不选择 nums[index]dfs(index+1);}

2. DFS 树

当前元素 / \ 选 不选 / \ 下一个元素 下一个元素

每一个元素都有：

2 个选择

3. 一句话记忆

子集：每一层决定“当前这个数要不要”。

八、五种 DFS 对比总结

九、看到 DFS 题，先问自己这 6 个问题

1. 我现在在哪一层？

例如：

全排列：第几个位置 迷宫：当前坐标 八皇后：第几行 组合：已经选了几个数 子集：正在考虑第几个元素

2. 这一层我到底在决定什么？

这是最重要的问题。

全排列 → 当前这个位置放什么？ 迷宫 → 下一步走哪里？ 八皇后 → 当前这一行放哪一列？ 组合 → 下一个选哪个数？ 子集 → 当前元素选不选？

3. 当前有哪些选择？

例如：

全排列： 1 ~ n 迷宫： 上下左右 八皇后： 1 ~ n 列 组合： start ~ n 子集： 选 / 不选

4. 哪些选择是不合法的？

例如：

全排列： 数字已经使用过 迷宫： 越界、障碍物、已经访问过 八皇后： 同列、同对角线已经有皇后

5. 什么时候结束递归？

也就是：

if(终止条件){...return;}

例如：

全排列： step > n 迷宫： 到达终点 八皇后： row > n 组合： 已经选择 k 个数 子集： 所有元素都考虑完

6. 递归回来以后恢复什么？

这就是：

回溯。

例如：

全排列： vis[i] = false 迷宫： vis[nx][ny] = false 八皇后： 撤销皇后占用状态 组合： path.pop_back() 子集： path.pop_back()

十、DFS 最终记忆模板

voiddfs(当前状态){if(到达终点){记录答案;return;}for(枚举当前层所有选择){if(选择合法){// 做选择修改状态;// 进入下一层dfs(下一个状态);// 回溯恢复状态;}}}

最后只需要牢牢记住一句：

“这一层我到底在决定什么？”

如果这个问题回答出来了，后面的 DFS 代码通常就能慢慢写出来。

十一、DFS 六问口诀

第一问：我现在在哪一层？ 第二问：这一层我要决定什么？ 第三问：我有哪些选择？ 第四问：哪些选择不能选？ 第五问：选完以后进入哪里？ 第六问：回来以后恢复什么？

最终浓缩成：

确定状态 → 枚举选择 → 判断合法 → 做选择 → DFS → 撤销选择。