DFS深度优先搜索

什么是深度优先搜索？

深度优先搜索（DFS）是搜索手段之一。是从某个状态开始不断转移状态直到无法转移为止，然后退回到前一步状态继续转移其他状态，可以想象为一个沿树爬行的虫子，在一个交叉口他会首先随机选择一条分岔路口一直走下去直到死路为止，然后会返回到这个交叉口沿着另一条分支爬行下去，直到遍历所有可能的路径为止。根据这个特点，DFS算法用递归来实现比较简单。

举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C,D），则我们可能得到如下的一个访问过程：A->B->E（没有路了！回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）。每次深度优先搜索的结果必然是图的一个连通分量。

直接看怎么用dfs解决问题，一道是阿里的面试题，一道是网易的。最后一道是利用剪枝的dfs，也是网易的。因为实现dfs大多时候使用递归，所以题里往往会有n比较小，或者可变的长短比较小等提示。还有一种特殊情况n较大，就是要用到剪枝～

一：

乍一看好像是可以用动态规划来做，但是因为涉及到交换操作，所以dp矩阵没法构造，这道题就是利用dfs来解决的。

假设我们有两个长度相同的字符串：A:[a1,a2,a3...，a5], B:[b1,b2,b3....,b5]。

那么我们选取的深度就是字符串的长度，从头到尾，计算操作的次数，得到最小的结果。

字丑，见谅。

知道每条路怎么走了，接下来就是代码实现

#include<bits/stdc++.h>
using namespace std;
int dfs(string& A,string& B,int loc);
int main(){
    int n;
    while (cin >> n){
        string a,b;
        getchar();
        getline(cin,a);
        getline(cin,b);
        int res = dfs(a,b,0);
        cout <<res<<endl;
    }
    return 0;
}
int dfs(string& A,string& B,int loc)
{
    if(loc==A.size())
        return 0;
    int counts=dfs(A,B,loc+1);
    //如果a1==b1，结果就是dfs(A,B,len+1),即不需要操作。
    if(A[loc]==B[loc])
        return counts;
    else{
        //不做交换需要的操作次数
        //要记得加上相等后 后面字符需要的交换数
        int no_swap=fabs(A[loc]-B[loc])+counts;
        int do_swap=INT_MAX;
        for(int i=loc+1;i<A.size();++i){
            //交换需要的操作次数
            int t=1+fabs(A[loc]-B[loc]);
            swap(A[loc],A[i]);
            //同理加上后面的操作数,这里交换了字符，所以不能用counts,需要重新递归调用
            t+=dfs(A,B,loc+1);
            swap(A[loc],A[i]);
            //选取一个交换后操作次数最少的。
            do_swap=min(do_swap,t);
        }
        return min(do_swap,no_swap);
    }
    return 0;//其他异常情况返回0
}

二：

数列还原，牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。

字丑，见谅。

知道怎么深度遍历了，就该敲代码了。

#include<bits/stdc++.h>
using namespace std;

//得到数组有序对的个数
int order_cnt(const vector<int>&v);
void dfs(int len,int n,int k,vector<pair<int,int>>&,vector<int>&);
int ans=0;
int main()
{	
	int n,k;
	vector<int>text(100,0);
	vector<int>record(100,0);
	vector<pair<int,int>>unshown;
	cin>>n>>k;
	for(int i=0;i<n;++i)
	{
		cin>>text[i];
		//record记录哪些数字出现了就为1 没出现为0
		record[text[i]]=1;
	}
	//利用record把那些没出现的数字放在unshown数组中
	for(int i=1;i<=n;++i)
		if(!record[i])unshown.emplace_back(make_pair(i,0));
	dfs(0,n,k,unshown,text);
	cout<<ans;
	return 0;
}
int order_cnt(const vector<int>&v)
{
	int cnt=0;
	for(int i=0;i<v.size();++i){
		for(int j=i+1;j<v.size();++j)
			if(v[j]>v[i])
				++cnt;
	}
	return cnt;
}
//len当前序列长度，n是总长度，k是要求的有序对数，unshown存放未出现的数字以及要用到的标记位
void dfs(int len,int n,int k,vector<pair<int,int>>&unshown,vector<int>&text)
{
	if(len==n){
		if(order_cnt(text)==k)++ans;
		return ;
	}
	if(text[len])dfs(len+1,n,k,unshown,text);
	else{
		for(int i=0;i<unshown.size();++i){
			//如果flag位是0，说明没用过。
			if(!unshown[i].second){
				unshown[i].second=1;
				text[len]=unshown[i].first;
				dfs(len+1,n,k,unshown,text);
                //用完了递归结束返回上一层，把标记位归零，上一层重新选取数字，所以又是没用过的状态。
				unshown[i].second=0;
				text[len]=0;
			}
		}
	}
}

什么是剪枝？

剪枝就是一种生动的比喻：把不会产生答案的，或不必要的枝条“剪掉”。

剪枝的关键就在于剪枝的判断：什么枝该剪，什么枝不该剪，在什么地方减。

就是在深度优先搜索的时候，不要一条路走到黑，满足一定条件的时候，直接跳出或者返回结果。

看题：一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

这个题可以理解为，n个球放在那里，你一个一个的放入袋子(袋子里面有一个)，总共能得到多少种幸运袋子。

因为这里有条件：sum>mul 因此利用这个来剪枝，我们把球按大小排序，从小的开始往袋子里放，通过观察计算可以发现，如果小号没法满足，大号就更无法满足了（因为因子增加明显比加数大）。

所以先对球进行排序，然后把最小的球1放入口袋(因为a+b>a*b的条件是a,b必须有一个为1，所以幸运口袋里第一个一定是1)

然后开始dfs，不满足条件的不需要继续往后递归，直接break,代码：

#include<bits/stdc++.h>
using namespace std;
int dfs(const vector<int>&A,int loc,int sum,int mul);
int main()
{
	int n;
	cin>>n;
	vector<int>balls(n,0);
	for(int i=0;i<n;++i)
		cin>>balls[i];
	sort(balls.begin(),balls.end());
	cout<<dfs(balls,0,balls[0],balls[0])<<endl;
	return 0;
}
int dfs(const vector<int>&A,int loc,int sum,int mul)
{
	int res=0;
	for(int i=loc+1;i<A.size();++i){
		int nowSum=sum+A[i];
		int nowMul=mul*A[i];
		if(nowSum>nowMul)
			res+=1+dfs(A,i,nowSum,nowMul);
		else break;
		while(i<A.size()-1&&A[i]==A[i+1])++i;

	}
	return res;
}