DFS

dfs深度优先搜索与剪枝模板

为什么要用dfs

• 提起dfs，最先会想到树和图的dfs，但算法中的dfs泛指一种暴力搜索的方式,即按照深度优先的次序来查找所有数据组合中符合需求的情况
• 与bfs（bfs先挖个坑）相比，dfs书写简单，容易理解只要你够闲的话多写亿个for循环也能搞出来，但容易爆栈，在使用时不要忘记观察数据范围，dfs大概率是过不了10的4次方以上的数据的

• 这里以洛谷p1025数的划分来举例讲解dfs

  [NOIP2001 提高组] 数的划分

题目描述

将整数 \(n\) 分成 \(k\) 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：\(n=7\)，\(k=3\)，下面三种分法被认为是相同的。

\(1,1,5\);
\(1,5,1\);
\(5,1,1\).

问有多少种不同的分法。

输入格式

\(n,k\) （\(6<n \le 200\)，\(2 \le k \le 6\)）

输出格式

\(1\) 个整数，即不同的分法。

样例 #1

样例输入 #1

7 3

样例输出 #1

4

提示

四种分法为：
\(1,1,5\);
\(1,2,4\);
\(1,3,3\);
\(2,2,3\).

【题目来源】

NOIP 2001 提高组第二题

---

• 这是一道经典的dfs搜索题，首先来尝试暴力写法

• 输出为一个整数，定义ans变量记录分法

• 首先看题目的条件，分成k个数，我们定义count变量，当count==k时，这种情况符合题意，同时，这k个数的总和要=n，我们定义sum变量，当count==k且sum==n时，ans++;

• 为了保证所有情况不重复，循环时要令后面的数大于等于前面的数

  import java.util.Scanner;
  
  public class Main {
  	static int suml,countl;
  	static int n,k,ans=0;//整数n,分成k份，有ans种方法
  	public static void main(String[] args) {
  		Scanner scan=new Scanner(System.in);
  		n=scan.nextInt();
  		k=scan.nextInt();
  		dfs(1, 0,0);
  		System.out.println(ans);
  		scan.close();
  	}
  	public static void dfs(int start ,int sum,int count) {//参数：去重起始位，总和，数字个数
  		if(count==k) {//如果数字个数达到k，判断后一定要返回，不然无限循环
  		if(sum==n) {//如果相加等于n,ans+1
  			ans++;
  		}
  		return;//一定要有递归出口！！！！递归出口一定要写对位置！！！不然就是个爆栈！！！
  		}
  		for (int i = start; i<=n; i++) {//去重，保证后一个数一定大于等于前一个数
  			suml=sum+i;countl=count+1;
  			dfs(i,suml,countl);
  			suml=sum-i;countl=count-1;
  		}
  	}
  }

  | | | | | | | | ## 剪枝

• 很显然，这种写法时间复杂度过高，无法通过所有测试用例,我们需要在for循环处做一些剪枝操作，不可能符合条件的值就不进入递归步骤

• 在写dfs时，习惯将判断条件放在最上面，剪枝等操作在进入递归前进行（for循环只是为了优化代码，不必要可以不写），递归前后要进行状态标记和状态回退

• 我们知道，枚举时后面的数一定大于等于前面的数，显然，当前的数i应符合这样的条件：sum+i*(k-count)<=n

• 以下是优化过的代码

  import java.util.Scanner;
  public class p1025数的划分dfs剪枝 {
  	static int n,k,ans=0;//整数n,分成k份，有ans种方法
  	public static void main(String[] args) {
  		Scanner scan=new Scanner(System.in);
  		n=scan.nextInt();
  		k=scan.nextInt();
  		dfs(1, 0,0);
  		System.out.println(ans);
  		scan.close();
  	}
  	public static void dfs(int start ,int sum,int count) {//参数：去重起始位，总和，数字个数
  		if(count==k) {//如果数字个数达到k，判断后一定要返回，不然无限循环
  		if(sum==n) {//如果相加等于n,ans+1
  			ans++;
  		}
  		return;//一定要有递归出口！！！！递归出口一定要写对位置！！！不然就是个爆栈！！！
  		}
  		for (int i = start; sum+i*(k-count)<=n; i++) {//去重，保证后一个数一定大于等于前一个数+减枝
  			dfs(i,sum+i,count+1);//可以这样写，也完成了状态标记和回退操作
  		}
  	}
  }