DFS 模板总结关键是“这一层到底在选择什么”DFS 最核心的思想不是死记代码而是先想清楚“这一层我到底在决定什么”只要这个问题想明白DFS 通常就知道该怎么写了。一、DFS 通用模板voiddfs(当前状态){// 1. 递归出口if(到达终点){记录答案;return;}// 2. 枚举当前这一层的所有选择for(所有可能的选择){// 3. 判断这个选择是否合法if(合法){// 4. 做选择修改状态;// 5. 进入下一层dfs(下一个状态);// 6. 回溯撤销选择恢复状态;}}}可以直接记成枚举选择 ↓ 判断是否合法 ↓ 做选择 ↓ 递归 ↓ 撤销选择回溯二、不同 DFS 题“选择”是不一样的这是最重要的部分。题型当前这一层在决定什么“做选择”通常写什么全排列当前这个位置放哪个数字a[step] i迷宫下一步往哪个方向走vis[nx][ny] true八皇后当前这一行皇后放在哪一列标记这一列和对角线组合当前选择哪个数进入答案path.push_back(i)子集当前元素选还是不选两次递归选 / 不选以后看到 DFS先问自己一句“这一层我到底在决定什么”三、全排列 DFS1. 这一层在选择什么假设要求1 2 3的所有排列。当step1;表示现在要决定第 1 个位置放哪个数字。可以选择1 2 3所以全排列中每一层是在选择“当前位置放哪个数字”。2. 模板intn;inta[10];boolvis[10];voiddfs(intstep){// 递归出口if(stepn){for(inti1;in;i)couta[i] ;cout\n;return;}// 枚举当前这个位置可以放哪个数字for(inti1;in;i){if(!vis[i]){// 做选择a[step]i;vis[i]true;// 进入下一层dfs(step1);// 回溯vis[i]false;}}}3. 这一题怎么理解“做选择”a[step]i;vis[i]true;表示第step个位置选择数字i。然后dfs(step1);表示当前这一位已经确定继续决定下一位。递归回来以后vis[i]false;表示撤销刚才的选择让数字i可以被其他排列继续使用。4. 一句话记忆全排列每一层决定“这个位置放谁”。四、迷宫 DFS1. 这一层在选择什么当前站在(x, y)下一步通常有四种可能上 下 左 右所以迷宫 DFS 每一层是在选择“下一步往哪个方向走”。2. 方向数组intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};分别表示上 下 左 右3. 模板voiddfs(intx,inty){// 到达终点if(xtxyty){ans;return;}// 枚举四个方向for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 越界if(nx1||nxn||ny1||nym)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. 一句话记忆迷宫每一层决定“下一步往哪里走”。五、八皇后 DFS1. 这一层在选择什么八皇后一般是一行一行放。例如dfs(row);表示当前正在决定第row行的皇后放在哪里。这一行可以枚举第 1 列 第 2 列 第 3 列 ... 第 n 列所以八皇后每一层是在选择“当前这一行放在哪一列”。2. 模板voiddfs(introw){// 所有行都放完if(rown){ans;return;}// 枚举当前这一行的每一列for(intcol1;coln;col){if(这一列和两个对角线都没有皇后){// 做选择标记这一列;标记两个对角线;// 进入下一行dfs(row1);// 回溯取消这一列标记;取消两个对角线标记;}}}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 41. 这一层在选择什么每一层是在决定下一个加入组合的是哪个数字。2. 模板vectorintpath;voiddfs(intstart){// 已经选够 k 个数if(path.size()k){// 输出答案return;}// 从 start 开始枚举for(intistart;in;i){// 做选择path.push_back(i);// 下一层从 i 1 开始dfs(i1);// 回溯path.pop_back();}}3. 这一题怎么理解“做选择”path.push_back(i);表示把数字i放进当前组合。然后dfs(i1);表示下一层从i1往后继续选。回来以后path.pop_back();表示撤销刚才加入的数字尝试其他选择。4. 一句话记忆组合每一层决定“下一个选哪个数”。七、子集 DFS例如集合{1, 2, 3}对于每一个元素都有两种选择选 不选所以子集问题每一层是在决定“当前元素选还是不选”。1. 模板vectorintpath;voiddfs(intindex){// 所有元素都考虑完if(indexn){// 输出当前子集return;}// 情况1选择 nums[index]path.push_back(nums[index]);dfs(index1);// 回溯path.pop_back();// 情况2不选择 nums[index]dfs(index1);}2. DFS 树当前元素 / \ 选 不选 / \ 下一个元素 下一个元素每一个元素都有2 个选择3. 一句话记忆子集每一层决定“当前这个数要不要”。八、五种 DFS 对比总结题型dfs()参数通常表示什么当前这一层在决定什么回溯什么全排列step当前第几个位置当前位置放哪个数字vis[i] false迷宫(x,y)当前坐标下一步往哪个方向走vis[nx][ny] false八皇后row当前第几行当前行放在哪一列列、对角线状态组合start从哪里开始选下一个选哪个数path.pop_back()子集index当前元素当前元素选还是不选path.pop_back()九、看到 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 → 撤销选择。
