🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏： 蓝桥杯算法笔记
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️为什么我们不知疲倦，因为我们都在做自己所热爱的事 ♐
@TOC
🚀write in front🚀
最近一直都在写蓝桥杯的题目，其中有许多题目涉及到了搜索（DFS，BFS）等，由于递归过于抽象，所以没能很好的掌握。于是便写下了这篇入门教程来加深对DFS的认识，并且充分理解递归。
所谓DFS就是指：优先考虑深度，换句话说就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。
一、💡DFS算法模板
解决一个DFS算法问题，实际上就是一个决策树的遍历过程。你只需要思考如下3个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法在做选择的条件。
如果你不理解这3个名词的解释，没关系，后面会用“全排列”相关题目经典问题来帮助你理解这些词语的含义，现在现有一个印象即可。
result= []
def backtrack(路径，选择列表)：
if(满足结束条件)：
result.add(路径)
return;
for 选择 in 选择列表：
做选择
backtrack(路径，选择列表)
撤销选择其核心就是for循环里面的递归，在递归调用之前“做选择”，在递归调用之后“撤销选择”。
什么叫撤销选择？这个框架的底层原理是什么呢？下面我们就通过全排列问题解开之前的疑惑，一探究竟吧！！！
二、💡全排列问题
🌸题目描述：
题目：
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
代码如下（示例）：输入格式
一个整数 n。输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。数据范围
1≤n≤9输入样例：
3输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
🌸思路分析：
🌸核心代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int n,state[N];
bool use[N];
void dfs(int u)//这里u表示第几个位置
{
if(u>n)
{
for(int i=1;i<=n;i++) printf("%d ",state[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++)
{
if(!use[i])
{
state[u]=i;
use[i]=true;
dfs(u+1);
//恢复原来的状态
state[u]=0;
use[i]=false;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}🌸总结
穷举和时间复杂度大是DFS算法的一个特点，不像动态规划存在重叠子问题可以优化，DFS算法就是纯暴力枚举，复杂度雀氏高。
明白了全排列问题，就可以直接套用DFS算法的模板了，下面就看新的问题。
三、💡递归实现指数型枚举
🌸题目描述
🌸思路分析：
🌸核心代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=16;
int n,st[N];
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
if(st[i]==1)
printf("%d ",i);
printf("\n");
return;
}
st[u]=2;
dfs(u+1);
st[u]=0;
st[u]=1;
dfs(u+1);
st[u]=0;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}🌸总结
套用模板就欧克了。
四、💡递归实现组合型枚举
🌸题目描述：
🌸思路分析：
DFSDFS模板
🌸核心代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30;
int st[N];
int n,m;
void dfs(int u,int start)
{
if(u==m+1)
{
for(int i=1;i<=m;i++)
printf("%d ",st[i]);
printf("\n");
return;
}
for(int i=start;i<=n;i++)
{
st[u]=i;
dfs(u+1,i+1);
st[u]=0;
}
}
int main()
{
scanf("%d %d",&n,&m);
dfs(1,1);
return 0;
}🌸总结
就是多写多练才会滚瓜烂熟这些题目，不然不思考永远都不会成为自己的东西。
