先申明

这里先申明，这个dfs总结是我自己个人的总结，如有冒犯，见谅

自己看一道题的思路

别人看一道题，会咋想，肯定是先确定算法嘛
我，先看一下可不可以dfs搜一下

1.确认是否可以使用dfs

像我这样的，基本看一眼就知道可不可以搜了（所以有的时候会判断错【捂脸哭】）
如果不知道或不确定的话，就要归宿到dfs的根源，树了

判断是否存在分类讨论

分类讨论其实就是dfs的思想，把每个过程都分类讨论，舍去无效答案，剩下的答案就是最终答案

判断是否可以把过程抽象成树

个人认为，dfs其实就是分类讨论，每次遇到一种情况，就开始分类讨论
分类的结果就是叶子结点，每个节点（除了叶子结点）都要再一次分类讨论
所以判断一道题是不是你 可以写出来的 dfs，最简单的方法就是抽象成树

2.dfs该咋搜

其实我，并没感受到dfs的博大精深
到我学的地方（普及组），我觉得dfs能分成3类

类1：万能搜
类2：路径搜
类3：记忆化

这里讲的就是万能搜

写万能搜的步骤

按照我的老师的说法，dfs应该根据树来写

但是我不一样！，我是根据模板来写的

（1）需要提前记住的东西

这里说的模板直接写，是需要你从分类讨论的角度来看题
比如每次分类的分法，最终答案会在哪，那些情况可以舍去等

做不到分类讨论咋办

那就桉树呗
与（1）对应的，这里需要记的是，树的宽度，叶子结点的层数，剪枝等

（2）模板走起

这里我给模板的每个位置起了名（如有雷同，还请见谅）

void/*或int*/ dfs(int step/*层数*/,int n/*树的宽度*/)	//这个地方叫传参区，一般传层数（step）,答案（ans）,树的宽度（n）,标记（flag） 
{if(){	//大剪枝区/*大剪枝区不经常出现在出现最小值时，目前的累计已经大于目前最优答案时，就直接return */ return;}if(/*截止区*/){//操作区/*在操作区里，你就要对这个答案是否合法或符合题目要求做判断了 */ }else{for(int i=1;i<=n;i++){	//分类讨论区 /*有时分类讨论区中，树的宽度是不定或不明确的那么我们也可以用while */if(!flag[i]){	//小剪枝区 /*当我们做一些问题时，每种东西只能用一遍，我们就可以标记，来小剪枝这是很必要的有些题目可能没有 */flag=1;//标记区sel[step]=i;	//答案区，这里不一定是这样，只是举个例子 dfs(step+1,n);	 //递归区flag=0;	//回溯区 }} } 
}

例

全排列问题
这里就是输出1~n的全排列
来根据上面的步骤来一步一步写

我们先拷一份模板

考虑传参：这里传参只需要树的层数吧（每层选一个树）
截止条件：当层数为n时
小剪枝：这里需要去重，因为每个数只能选一遍
答案：用sel数组存储答案，在操作区输出
大剪枝区：这里需要思考有没有，这里是没有的
分类讨论：每次分类讨论都是固定的（1~n），所以直接用for就行了

这时候直接对应这填进去吧

#include <iostream>
#include <cstdio>
using namespace std;
const int N=40;
int n;
int sel[N];
int flag[N];
void dfs(int step){if(step==n+1){for(int i=1;i<=n;i++){printf("%5d",sel[i]);}cout<<endl;}else{for(int i=1;i<=n;i++){if(!flag[i]){flag[i]=1;sel[step]=i;dfs(step+1);sel[step]=0;flag[i]=0;}}}
}
int main(){cin>>n;dfs(1);return 0;
}

很简单吧

关于写dfs需要注意的地方

前面说过，dfs虽然说万能，但其实只能解70%不到的题目（比如今年的csp-j，四题一个没有可以搜的，把我人卡死了）

当你能确定这道题可以用dfs时，先确定这个dfs能拿多少分

1范围

这时候你先注意一下范围，画一下树，算出有多少节点，就是多少次运算
估一下，到多少时就会爆TLE，再进行优化或二次剪枝

2.printf和scanf

只要是dfs，就一定要用printf和scanf
这是很必须的
（因为我被这玩意卡了不知道多少次了）

当然，能用快读是最好，但是普及组不会卡快读的

3.调试

dfs是递归运算，所以在陌生的编译器里，该怎么调试呢

这里建议cout调试，每次输出当前的参数，来看变化，是否把不该剪的剪枝了

建议在答案区和操作区进行调试，只要确定一道题目可以dfs，那就绝对可以调出一个正确的代码，就算调了很久后还是没调出来，你就可以直接放弃（这里是有依据的，因为一般的出错都是存在于优化的时候出了错，所以正确答案还是存在于搜索树的叶子结点上的，所以一定会出现正确的情况）

4.心态

写dfs时，千千万万就是不能心态崩
当你拿出一手dfs，就不要想着把这题AC了，而是想着怎么正确的优化，拿更多分
dfs和其他算法不同，优化是一步一步的，而真正可以拿dfs AC的题目，一般都是出题者没有卡这个东西

dfs永远是一个底牌（虽然我看题都是第一个想到dfs的）

预祝我的同学们市赛考出个好成绩