【蓝桥杯刷题冲刺辅导】掌握递归·DFS解题套路，这一文足以？_递归恢复现场

大家好，我是安然无虞。

目录

一、刷题前和铁汁们唠一唠

1.刷题前须知

2.刷题时套路

<1>套路

<2>背下列常用数

​

<3>投机取巧：根据数据范围确定算法

​

<4>珍惜每分每秒 · 直接复制粘贴 

<5>输入输出函数的使用

二、刷题强化

例一：递归实现指数型枚举

例二：递归实现排列型枚举

例三：递归实现组合型枚举

例四：背包问题（DFS解法）

三、思考题：带分数

四、结语：遇见安然遇见你，不负代码不负卿！

---

【前言】

蓝桥杯刷题冲刺辅导专栏正式开启，小伙伴们快上车，下一站：翻身。

 

一、刷题前和铁汁们唠一唠

1.刷题前须知

大家如果对于基础算法的概念还不是特别理解，可以先回头看看这个专栏，写的比较基础哦。

蓝桥杯常考算法剖析_安然无虞的博客-CSDN博客https://blog.csdn.net/weixin_57544072/category_11418082.html好嘞，那么现在进入主题：

【敲黑板】

1. 刷题量：省赛好成绩 == 200题；国赛好成绩 == 300题
2. 调试技巧：好好练习调试，这是一个必须经历的过程，一道算法题，可能写出来只需要几分钟，但是想把一些边界或是特殊情况全都考虑的面面俱到就需要调试了，而且一道题目调试成功花费30分钟也是一件很正常的事情。
3. 学算法，一定要落实到代码上！万万不可懒惰哦。

2.刷题时套路

<1>套路

根据题目描述——>抽象出模型

<2>背下列常用数

<3>投机取巧：根据数据范围确定算法

<4>珍惜每分每秒 · 直接复制粘贴 

进入考场，我们最好将下列头文件和主函数写到电脑的记事本里，这样的话，每写一个程序时直接复制粘贴即可，把时间省下来用于后面难题的调试！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main()
{
 
	return 0;
}

<5>输入输出函数的使用

如果数据范围n < 100000，那么二者差不多；

如果数据范围n > 100000，那么用scanf 和 printf会更快，避免因为输入输出库函数本身超时 

二、刷题强化

注意哦，其实所有的递归题目都可以转换成一棵递归搜索树，当我们想不明白的时候可以画出递归搜索树，之前关于递归部分的讲解已经很清楚咯，如果大家还不是很理解的话可以看看那个专栏哦，在这里呢就用一句话概括了，递归就是自己调用自己。

例一：递归实现指数型枚举

题目描述：

解题思路：

本题有两个分支，一个是不选，一个是选。

 代码执行：

方法一：直接dfs暴力输出

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>//其实用不了这么多头文件，但是因为经常使用就直接粘贴了
 
using namespace std;
 
const int N = 16;
int n;//全局变量不初始化默认值为0，但是注意，局部变量不初始化是随机值
int st[N];//记录每个位置当前的状态，0表示暂时没选，1表示选它，2表示不选它
 
void dfs(int u)
{
    //找边界
    if(u > n)
    {
        for(int i = 1; i <= n; i++)
        {
            if(st[i] == 1)//注意哦，选了才要打印，没选打印个der（我之前就在这里错了）
                printf("%d ", i);
        }
        puts("");//puts("")可以自动换行，等价于printf("\n")和putchar('\n');
        return;//返回之前将前面的数据打印出来
    }
    st[u] = 2;
    dfs(u+1);//第一个分支不选
    st[u] = 0;//恢复现场-其实这行代码可不加，加上去是为了告诉大家每一层递归调用结束都要恢复现场（去的时候什么样，回来的时候什么样，做一个公平的爸爸）
    
    st[u] = 1;
    dfs(u+1);//第二个分支选  
    st[u] = 0;//恢复现场
}
int main()
{
    scanf("%d", &n);
    
    dfs(1);
    
    return 0;
}

方法二：用二维数组记录所有方案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
const int N = 16;
int n;
int st[N];//记录状态，0表示还没选，1表示选它，2表示不选它
vector<vector<int> > ways;//用二维数组记录所有方案
 
void dfs(int u)
{
    vector<int> way;
    //找边界
    if(u > n)
    {
        for(int i = 1; i <= n; i++)//记录方案
        {
            if(st[i] == 1)
            {
                way.push_back(i);
            }
        }
        ways.push_back(way);
        return;
    }
    st[u] = 2;
    dfs(u+1);//第一个分支不选
    st[u] = 0;//恢复现场-其实这行代码可不加，加上去是为了告诉大家每一层递归调用结束回溯都要恢复现场
    
    st[u] = 1;
    dfs(u+1);//第二个分支选
    st[u] = 0;//恢复现场
}
 
int main()
{
    scanf("%d", &n);
    dfs(1);
    for(int i = 0; i < ways.size(); i++)
    {
        for(int j = 0; j < ways[i].size(); j++)
        {
            printf("%d ",ways[i][j]);
        }
        puts("");
    }
    return 0;
}

是不是很简单，直接暴力求解就行了，但是我个人觉得方法一更简单些，你觉得嘞？ 

例二：递归实现排列型枚举

题目描述：

 解题思路：

依次枚举每个位置放哪个数

 代码执行： 

方法一：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int N = 10;
int n;
int state[N];//记录状态，0表示还没放数，1~n表示放了哪个数
bool used[N];//判重数组，true表示该位置用过了，false表示还没用过
 
void dfs(int u)
{
    //找边界
    if(u > n)
    {
        for(int i = 1; i <= n; i++)
        {
            if(state[i] != 0)//其实这条判断语句可省略，加上去是为了方便大家理解
            {
                cout << state[i] << ' ';   
            }
        }
        puts("");
        return;
    }
    
    //依次枚举每个分支，即当前位置可以填哪些数
    for(int i = 1; i <= n; i++)
    {
        if(!used[i])//该位置没用过时进来（即该位置还空着）
        {
            state[u] = i;
            used[i] = true;
            dfs(u+1);
            used[i] = false;//撤销标记
            //恢复现场-可以不写，这里加上为了方便大家理解
            state[u] = 0;    
        }
    }
}
 
int main()
{
    cin >> n;
    
    dfs(1);
    
    return 0;
}

方法二：

利用C++自带的STL，在标准头文件#include<algorithm>下的next_permutation()；其实在之前的专栏里面已经讲解过咯，不知道的铁汁们记得去看哦，这里我就不跟大家说这基本定义了。

【注意】：蓝桥杯时可以使用next_permutation()的，所以不用白不用！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int N = 10;
int n;
int state[N];
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        state[i] = i + 1;
    }
    do
    {
        for (int i = 0; i < n; i++)
        {
            printf("%d ", state[i]);
        }
        puts("");
    } while (next_permutation(state, state + n));
    return 0;
}

例三：递归实现组合型枚举

题目描述：

解题思路：

代码执行：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int N = 30;
int n,m;
int way[N];
 
void dfs(int u, int start)
{
    //找边界
    if(u > m)
    {
        for(int i = 1; i <= m; i++)
        {
            printf("%d ", way[i]);
        }
        puts("");
        return;
    }
    for(int i = start; i <= n; i++)
    {
        way[u] = i;
        dfs(u+1, i+1);
        way[u] = 0;//恢复现场
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    dfs(1,1);
    return 0;
}

其实这道题目还可以优化，感兴趣的小伙伴可以研究一下哈。 

到这里，经典的排列组合问题讲解的差不多了，大家要注意对比哟！

例四：背包问题（DFS解法）

这是上次在基础算法中就已经讲解过的一道题，很重要，大家要注意理解哈，后面讲到背包专题时就容易上手啦。

题目描述：
有n件物品，每件物品的重量为w[i], 价值为c[i]。现在需要选出若干件物品放入一个容量为v的背包中，使得在选入背包的物品重量和不超过容量v的前提下，让背包中物品的价格之和最大，求最大价值。

示例：

输入：物品重量：3 5 1 2 2  物品价值：4 5 2 1 3
 
输出：10

解题思路：
在这个问题中，需要从n件物品中选择若干件物品放入背包，使它们的价值之和最大。这样的话，对每件物品都有选和不选两种选择，而这就是所谓的“岔道口”。而当完成对于n件物品的选择之后就到达了“死胡同”，不过本题需要额外再多考虑一种情况，题目要求选择的物品总和不能超过v，因此一旦选择的物品重量总和超过v,也就会到达“死胡同”，所以这道题目需要多考虑一下，铁汁们要小心哦，具体的看代码实现。

代码执行：

//题目：有n件物品，每件物品的重量为w[i],价值为c[i](由于每件都不同，所以采用i表示变化的意思)。现在需要选出若干件物品放入一个
//容量为V的背包中，使得在选入背包的物品重量和不超过V的前提下，让背包中物品的价值之
//和最大，求最大价值(1 <= n <= 20)
 
#include<stdio.h>
 
int maxValue = 0;//最大价值
//下面四组数据可以自己设定，由于想简化题目所以在这里直接以全局变量的形式给出
int n = 5;//物品数目
int v = 8;//背包容量
int w[] = { 3,5,1,2,2 };//w[i]为每件物品重量
int c[] = { 4,5,2,1,3 };//c[i]为每件物品价值
 
//index为当前处理物品的下标（物品下标范围是0~n - 1）
//sumW和sumC分别为当前总重量和当前总价值
void DFS(int index, int sumW, int sumC)
{
    //已经完成了对n件物品的选择（递归边界--死胡同）
    if (index == n)
    {
        return;
    }
    //岔道口
    DFS(index + 1, sumW, sumC);//不选第index件物品
 
    //只有加入第index件物品后未超出容量v,才能继续执行（注意这个限制条件）
    if (sumW + w[index] <= v)
    {
        //注意哦，如果加入第index件物品后总价值大于最大价值maxValue时记得要更新最大价值
        if (sumC + c[index] > maxValue)
        {
            maxValue = sumC + c[index];//更新最大价值maxValue
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);//选择第index件物品
    }
}
int main()
{
    DFS(0, 0, 0);//初始时为第0件物品、当前总重量和总价值均为0
    printf("满足条件的最大价值为：%d\n", maxValue);
    return 0;
}

三、思考题：带分数

题目描述：

解题思路：

本题可以强化自己对于排列性枚举的理解，哈哈，大家先尝试做一下哈，下篇会详细讲解。

四、结语：遇见安然遇见你，不负代码不负卿！

在这里向催更的铁汁们说声对不起，由于我最近在补课，所以整理刷题慢了下来，不过铁汁们请放心，现在已经开始更新咯，快快上车！