手把手学会DFS (递归入门)

目录

算法介绍

递归实现指数型枚举

递归实现排列型枚举

递归实现组合型枚举


算法介绍

🧩DFS Depth First Search ,中文又叫深度优先搜索,是一种沿着树的深度对其进行遍历,直到尽头之后再进行回溯,再走其他路线的方法,在对数据进行枚举,或求子串数量时具有奇效。该算法的实现取决于递归,因此如何设置递归的结束条件,以及什么时候调用递归便显得十分重要。

🧩通过 DFS 进行遍历,便可以无遗漏地走遍整个树,再根据题目要求在特定的位置对数据进行处理或输出。

🧩最重要的一点便是,当我们一条路走到底之后,就要回溯,就像上图中 3 5 6 步那样回到上一个节点。之后会判断是走另外一条路还是再回溯到上一层,由于在回溯前我们就已经对数据进行了处理,所以要对数据进行还原,即回溯到第一次到达这个节点时的那份数据。具体的细节就留到题目里面讲吧。

递归实现指数型枚举

传送门:AcWing 92. 递归实现指数型枚举

🧩DFS 的入门题,要求在 1~n 之间找所有可能出现的子序列的情况。可以全选也可以全部都不选,但输出的方式就比较宽松不需要特别处理。

🧩于是我们就可以将 1~n 的每一位都看作有两个选择选和不选,用一个数组存储。每次到达叶节点的时候便完成一次枚举,并输出。而每次递归参数就加一,表示往下一层,位数的增加。注意的细节都写在代码里了,结合代码进行理解。

如果比较难想象一定要画递归图!!!!

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 15;
int n;
int sta[N];  //状态数组,表示当前位的数选或不选

void dfs(int i)
{
    if(i == n)  //位数等于n,表示所有数的状态都已确定,可以进行输出
    {
        for(int j = 1;j<=n;j++)
        {
            if(sta[j] == 1)
            {
                printf("%d ",j);
            }
        }
        puts("");
        return;
    }
    sta[i+1] = 1;  //1表示选该数字
    dfs(i+1);      //往下一层递归
    sta[i+1] = 0;  //回溯后重置,但其实下面就会覆盖掉加不加没区别,只是为了好理解
    
    sta[i+1] = 2;  //2表示不选
    dfs(i+1);
    sta[i+1] = 0;
}

int main()
{
    scanf("%d",&n);
    dfs(0);        //从第0层开始
    
    return 0;
}

递归实现排列型枚举

🧩传送门:AcWing 94. 递归实现排列型枚举

🧩依题意,一个 1~n 的整数要输出其所有的排列情况,这便于上一题不同了,上一题是每位数的相对位置都是固定的,输出长度是不固定的。但这题固定长度,但每个位的数字并不是固定的。那我们便可以从每位出发,枚举每一位可能出现的数字,但每个数字都只能出现一次。因此需要一个数组记录这个数字是否被使用过。递归结束时输出当前方案,再进行回溯。

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 10;
int n,count;
int sta[N];     //用于存储方案
bool used[N];   //有没有被用过

void dfs(int i)
{
    if(i>n)  //从1开始递归则判断条件为i>n从0开始则是i=n结束递归
    {
        for(int j = 1;j<=n;j++) printf("%d ",sta[j]); //输出
        puts("");
        return;
    }
    
    for(int j = 1;j<=n;j++)  //寻找还没有用过的数
    {
        if(!used[j])  //true表示用过,false表示未用
        {
            sta[i] = j;  //i位置选j
            used[j] = true; //标记j已使用
            dfs(i+1);    //往下一位递归
            
            used[j] = false; //回溯后当前位就不使用了于是置为false
        }
    } //之后继续寻找下一个没有用过的数
}

int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

递归实现组合型枚举

🧩传送门:AcWing 93. 递归实现组合型枚举

🧩这题就有点像上面两题的结合版,给定 1~n 的范围输出指定长度的从小到大的全部排列。要注意的是输出的情况是严格递增的,即不会出现中途有数字小于前面数字的情况。所以在查找没用过的数字时,需要从上一位加一开始查找。只有位数达到标准了才输出,因此会筛选掉一些不符合要求的答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 26;
int n, m;
int sta[N];   //用于存储方案
bool used[N]; //有没有被用过
void dfs(int x)
{
    if (x > m)  //位数符合,可以输出
    {
        for (int i = 1; i <= m; i++)
        {
            printf("%d ", sta[i]);
        }
        printf("\n");
        return;
    }
    for (int i = sta[x - 1] + 1; i <= n; i++) //由于输出是严格递增的由此当前位一定比上一位大
    {
        if (!used[i])  //当前数未被用则进行操作,否则跳过
        {
            sta[x] = i;  //当前位置选i
            used[i] = true; //标记当前位置已使用
            dfs(x + 1);  //向下递归
            used[i] = false; //状态回溯
        }
    } //之后继续寻找下一个没有用过的数
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1);
    return 0;
}

🧩好了这次DFS的入门讲解到这里就结束了,如果对你有用的话还请留下你的三连加关注。算法的学习还是建立在多练习上,学会了思想还需要多多实践才能熟练地掌握。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/913.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

springboot复习(黑马)

学习目标基于SpringBoot框架的程序开发步骤熟练使用SpringBoot配置信息修改服务器配置基于SpringBoot的完成SSM整合项目开发一、SpringBoot简介1. 入门案例问题导入SpringMVC的HelloWord程序大家还记得吗&#xff1f;SpringBoot是由Pivotal团队提供的全新框架&#xff0c;其设计…

GPT-4技术报告

摘要 链接&#xff1a;https://cdn.openai.com/papers/gpt-4.pdf 我们汇报了GPT-4的发展&#xff0c;这是一个大规模的多模态模型&#xff0c;可以接受图像和文本输入并产生文本输出。虽然在许多现实场景中&#xff0c;GPT-4的能力不如人类&#xff0c;但它在各种专业和学术基…

数智链接,新一代校园招聘解决方案

疫情3年市场巨变&#xff0c;00后新生代初登上求职舞台&#xff0c;中和作用下&#xff0c;牛客发现新生代求职发生明显变化&#xff0c;企业校招也要随之而变&#xff0c;并率先提出以种草、精准、专业为特点的新一代校园招聘解决方案。01.学生求职变了&#xff01;安全感、非…

奇异值分解(SVD)原理与在降维中的应用

奇异值分解(SVD)原理与在降维中的应用 奇异值分解(Singular Value Decomposition&#xff0c;以下简称SVD)是在机器学习领域广泛应用的算法&#xff0c;它不光可以用于降维算法中的特征分解&#xff0c;还可以用于推荐系统&#xff0c;以及自然语言处理等领域。是很多机器学习算…

GPT-4来袭:开启人工智能新时代

文章目录介绍GPT4 模型演示示例示例 1示例 2示例 3示例 4示例 5最后Reference介绍 2023年3月15日&#xff0c;OpenAI公司正式发布了先进的自然语言处理模型GPT-4&#xff0c;前不久发布的GPT-3.5模型只能理解文字的语言模型&#xff0c;而新发布的GPT4则是多模态模型&#xff…

【java】了解常见集合类

了解常见集合类 一、集合类框架 1、集合类框架结构图 首先我们要对集合类结构有一个大体的认识&#xff0c;所有集合都继承于迭代器&#xff0c;分为单列集合和映射集合&#xff0c;单列集合分为有序可重复和有序不可重复&#xff0c;大概结构如下图所示 2、主要集合类的介…

你真的知道如何系统高效地学习数据结构与算法吗?

文章目录前言&#xff1a;什么是数据结构&#xff1f;什么是算法&#xff1f;学习这个算法需要什么基础&#xff1f;学习的重点在什么地方&#xff1f;一些可以让你事半功倍的学习技巧1.边学边练&#xff0c;适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…

文心一言---中国版的“ChatGPT”狂飙的机会或许要出现了

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

linux 基础

1.Shell 命令的格式如下&#xff1a;command -options [argument]command: Shell 命令名称。options&#xff1a; 选项&#xff0c;同一种命令可能有不同的选项&#xff0c;不同的选项其实现的功能不同。argument&#xff1a; Shell 命令是可以带参数的&#xff0c;也可以不带参…

【计算机二级Python】综合题目

计算机二级python真题 文章目录计算机二级python真题一、简单应用——明星投票二、综合应用题《评奖学金 两问》一、简单应用——明星投票 描述使用字典和列表型变量完成最有人气的明星的投票数据分析。投票信息由附件里的文件vote.txt给出,一行只有一个明星姓名的投票才是有效…

【BLE 5.3无线MCU CH582】1、初识CH582开发板(开箱)

1、认识板子 优点&#xff1a; &#xff08;1&#xff09;引脚全部引出&#xff1b; &#xff08;2&#xff09;USB下载程序&#xff1b; &#xff08;3&#xff09;TYPE-C接口好评&#xff1b; &#xff08;4&#xff09;板载连个两个USB口&#xff0c;都可以供电&#xff1b;…

前端性能优化之HTTP缓存

前端缓存 前端缓存可分为两大类&#xff1a;HTTP 缓存和浏览器缓存。 我们今天重点是 HTTP 缓存&#xff0c;下面这张图是前端缓存的一个大致知识点&#xff1a; HTTP 缓存 首先解决困扰绕人们的老大难问题&#xff1a; 一、什么是HTTP缓存&#xff1f; HTTP 缓存会存储与请…

六个实用技巧让你轻松写出优雅的链表代码

文章目录&#x1f4d5;前言&#xff1a;如何轻松写出正确的链表代码&#xff1f;&#x1f4d6;技巧一&#xff1a;理解指针或引用的含义&#x1f4d6;技巧二&#xff1a;警惕指针丢失和内存泄漏&#x1f4d6;技巧三&#xff1a;利用哨兵简化实现难度&#x1f4d6;技巧四&#x…

HTTP 协议

文章目录1. 前言2. HTTP 协议3. fiddler 的安装与认识4. HTTP 协议报文格式4.1 请求4.2 响应5. 构造 HTTP 请求5.1 基于 form 表单构造 HTTP 请求5.2 基于 ajax 构造 HTTP 请求6. postman7. HTTPS7.1 加密7.2 HTTPS 的工作过程1. 前言 前面几篇文章 &#xff0c; 说了关于 前端…

C++继承[万字详解]

目录 一.继承的介绍 1.1、继承的概念 1.2、继承的定义 1.2.1、定义格式 1.2.2、继承关系和访问限定符 1.2.3、继承基类成员后&#xff0c;在子类中成员访问方式的变化 二.基类和派生类对象赋值转化 三.继承中的作用域 四.派生类的默认成员函数 ★派生类的构造函数 派…

有关pytorch的一些总结

Tensor 含义 张量&#xff08;Tensor&#xff09;&#xff1a;是一个多维数组&#xff0c;它是标量、向量、矩阵的高维拓展。 创建 非随机创建 1.用数组创建 将数组转化为tensor np.ones([a,b]) 全为1 #首先导入PyTorch import torch#数组创建 import numpy as np anp.arr…

4.类的基本概念

目录 4.1 类的概述 类是一种活动的数据结构 4.2 程序和类&#xff1a;一个快速实例 4.3 声明类 ​4.4 类成员 4.4.1 字段 1.显示和隐式字段初始化 2. 声明多个字段 4.4.2 方法 4.5 创建变量和类的实例 4.6 为数据分配内存 合并这两个步骤 4.7 实例成员 4.8 访问修饰…

2023年天津市逆向re3.exe解析(超详细)

2023年天津市逆向re3.exe解析 1.拖进IDA里进行分析2.动态调试(过程省略了)3.解密加密算法4.输入FLAG 回显成功!1.拖进IDA里进行分析 打开后是这么一个程序,直接找到main函数f5反编译即可,这里要注意程序第一次反编译出的代码会有点问题,需要点进引用的那些其他sub函数里面…

【面试题】闭包是什么?this 到底指向谁?

一通百通&#xff0c;其实函数执行上下文、作用域链、闭包、this、箭头函数是相互关联的&#xff0c;他们的特性并不是孤立的&#xff0c;而是相通的。因为内部函数可以访问外层函数的变量&#xff0c;所以才有了闭包的现象。箭头函数内没有 this 和 arguments&#xff0c;所以…

百度将?百度已!

仿佛一夜之间&#xff0c;创业公司OpenAI旗下的ChatGPT就火遍全球。这是一场十分罕见的科技盛宴。下到普通用户&#xff0c;上到各科技大厂都在讨论ChatGPT的前景&#xff0c;国外的微软、谷歌&#xff0c;国内的百度、腾讯、阿里等等都在布局相关业务。比尔盖茨更是称ChatGPT与…