我要评论蓝桥杯不会dfs就好像刘备失去了诸葛亮一样，啊啊啊啊啊dfs真的很重要啊，要不然我也不会花时间在这总结，可恶，总结完我就去看熊出没大电影去。好了，来看一下蓝桥杯最常考的dfs类型题吧！！！
1.dfs实现排列型枚举
核心思路：枚举每个位置应该填哪一个数。
先来看一下排列什么意思：从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
就是要考虑顺序，求全排列是很经典的一个dfs模板题，暴力枚举的思路是这样的，m个位置，依次枚举每一个位置应该填哪一个数。
public class test14 {
static int n=1000000;
static int[]a=new int[n];
static boolean[]st=new boolean[n];
static int n;
public static void main(string[] args) {
scanner sc=new scanner(system.in);
n = sc.nextint();
dfs(1);
}
public static void dfs(int u){
if(u>n){
for (int i =1; i <=n ; i++) {
system.out.print(a[i]+" ");
}
system.out.println();
return;
}
for (int i=1;i<=n;i++){
if(!st[i]){
a[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
}
}
蓝桥杯考全排列的思路多了去了，学会这个算法就可以做蓝桥杯里面的很多题了，因为蓝桥杯听说也被称为暴力杯，考dfs的题很多很多.......
光说不练也不行，下面来个典型例题练练手，链接在这里1.带分数 - 蓝桥云课 (lanqiao.cn)
很容易想到暴力的思路，n=a+b/c，可以求出1-9的全排列然后枚举加法和乘法的位置，判断等式是否成立。
求全排列我们已经掌握了，那么如何枚举加号和除号的位置呢？
很显然，一共九个数，加号的前面只能有1-7个数，除号可以紧跟加号后面，但最多要给c留一位数，经过分析，不难写出下面的这段代码：
public static void check(){
for (int i = 1; i <=7 ; i++) {
for (int j = i+1; j <=8 ; j++) {
a=toint(1,i);
b=toint(i+1,j);
c=toint(j+1,9);
}
if(n*c==a*c+b){
ans++;
}
}
}toint函数的实现也很简单，如下
public static int toint(int start,int end){
int num=0;
for (int i = start; i<=end ; i++) {
num=num*10+arr[i];
}
return num;
}
实现了这些，这道题对我们来说不就轻轻松松了吗？
拿下这道题之后，我们可以趁热打铁试一下这几道dfs的题目，相信我们更能加深对dfs算法的理解：
2.递归实现指数型枚举
核心思路：枚举每一个thing的状态；
从 1∼n1∼� 这 n� 个整数中随机选取任意多个，输出所有可能的选择方案。
每个数有若干种状态，我们只需要枚举每个数的每一个状态就可以了，对于本道题，每个数只有选或不选两种状态，因此我们可以考虑使用dfs解决。
import java.util.arraylist;
import java.util.scanner;
//递归实现指数型枚举；
public class main {
static int n=16;
static int n;
static int[]st=new int[n];
static arraylist<arraylist<integer>>res=new arraylist<>();
public static void main(string[] args) {
scanner sc=new scanner(system.in);
n = sc.nextint();
dfs(1);
for (int i=0;i<res.size();i++){
for (int j=0;j<res.get(i).size();j++){
system.out.print(res.get(i).get(j)+" ");
}
system.out.println();
}
}
public static void dfs(int u){
if(u>n){
arraylist<integer>way=new arraylist<>();
for (int i=1;i<=n;i++){
if(st[i]==1){
way.add(i);
}
}
res.add(way);
return;
}
st[u]=2;
dfs(u+1);
st[u]=0;
st[u]=1;
dfs(u+1);
st[u]=0;
}
}
这里的st数组有三个值，0---代表还没考虑，1-----代表选这个数，2------表示不选当前这个数，dfs之后不要忘了回溯。
下面上真题：
面对这种题，我们会dfs！！！
依次枚举每道题，每道题有正确或错误两种状态，这样dfs的参数我们也可以很轻松的明确，dfs(int u,int score) u表示当前正在枚举第几道题目，score则表示当前获得的分数。
写好了参数之后，来写一下递归出口吧！
if(u>31){
return;
}
if(score==100){
return;
}
if(score==70){
ans++;
}
下面枚举答题正确和错误两种状态
dfs(u+1,score+10);
dfs(u+1,0);
怎么样？意犹未尽吗？那就再来几道题吧！！！
3.递归实现组合型枚举
组合与排列不同，组合不考虑顺序.
组合数公式是指从 n 个不同元素中，任取 m(m≤n) 个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合；从 n 个不同元素中取出 m(m≤n) 个元素的所有组合的个数，叫做 n 个不同元素中取出 m 个元素的组合数。用符号 c(n,m) 表示。(百度百科）
和枚举排列型的时候类似，那么我们怎么去重呢，因为1 2 3 和 2 3 1 and 3 2 1我们都会搜到，我们只想要一个组合就好了呀！
我们可以只需要数字从小到大的排列，再写函数参数的时候加上一个start,来表示当前位置从哪个数开始枚举，就可以完全解决这个问题；
dfs(int u,int start) u表示正在枚举第几个位置，start表示从哪一个数字开始枚举。
下面上代码：
public class test02 {
//递归实现组合型枚举；
static int n=20;
static int[]a=new int[n];
static int n,m;
public static void main(string[] args) {
scanner sc=new scanner(system.in);
n = sc.nextint();
m=sc.nextint();
dfs(1,1);
}
public static void dfs(int u,int start){
if(u+n-start<m){
//如果把后面的选完也不能凑够n个数，剪枝；
return;
}
if(u>m){
for (int i = 1; i <=m ; i++) {
system.out.print(a[i]+" ");
}
system.out.println();
}
for (int i = start; i <=n ; i++) {
a[u]=i;
dfs(u+1,i+1);
a[u]=0;
}
}
}
怎么样，是不是感觉到了dfs的神奇之处了呢，下面我们说这种类型的题目，不同的是这道题用到了并查集这个小东西。
4.dfs+并查集
发表评论