AcWing算法学习---dfs
🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:蓝桥杯算法笔记
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️为什么我们不知疲倦,因为我们都在做自己所热爱的事 ♐
文章目录
🚀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;
}
🌸总结
就是多写多练才会滚瓜烂熟这些题目,不然不思考永远都不会成为自己的东西。
相关文章
- 17个机器学习的常用算法!
- 深度学习笔记三:反向传播(backpropagation)算法[通俗易懂]
- 算法学习<1>---二分查找
- 算法学习<2>---选择排序
- 关于最短路径算法的理解
- EM算法及其推广
- 一种快速判断点在多边形内的算法
- 树链剖分 算法学习
- 化三角矩阵计算行列式的算法实现
- 8个常见的机器学习算法的计算复杂度总结
- [量化投资]你的机器学习算法真的能准确预测股价吗?
- JavaScript专项算法题(1):回调和高阶函数
- 机器学习算法竞赛实战-数据探索
- A.机器学习算法入门教程(一): 基于逻辑回归的分类预测
- KMP算法
- 算法-构建乘积数组详解编程语言
- 基于深度学习的人脸自动美妆与深度哈希算法
- CCF ADL 78 深度学习讲习班回顾:这几个大热领域的算法到应用,8位学术大牛带你掌握人工智能前沿技术
- JAVA算法起步之插入排序实例