DFS+回溯+剪枝（深度优先搜索）——搜索算法

目录

一、递归

1.什么是递归？

2.什么时候使用递归？

3.如何理解递归？

4.如何写好递归？

二、记忆化搜索（记忆递归）

三、回溯

四、剪枝

五、综合试题 

1.N皇后

2.解数独 

---

        DFS也就是深度优先搜索，比如二叉树的前，中，后序遍历都属于DFS。其本质是递归，要学好DFS首先需要掌握递归。接下来咱们就一起来学习DFS涉及的算法。

一、递归

1.什么是递归？

递归可以这样理解把它拆分出来，两个字，“递”和“归”
递：递推（这就需要找到递推公式）
归：回归（需要找到回归条件，递推过程逐渐逼近回归条件）

直白一点来说就是，一个函数自己调用自己的情况，当然一定是要能够返回的。

二叉树的遍历，快排，归并中都用到了递归。

2.什么时候使用递归？

        满足以下条件通常都能使用递归解决：在主问题中能找到相同的子问题，在子问题中又能找到相同的子问题。

        注意：递归过程，也就是在前一个函数没有销毁的时候调用下一个相同函数，调用函数就需要开辟函数栈帧，会占用大量空间，所以递归层数太多会导致栈溢出，解决不了问题。

        缺点：递归算法会占用大量内存，有栈溢出的风险，在实际开发中要尽量减少递归算法的使用。

        优点：递归算法简单明了，容易被想到，代码也是非常的好写。

3.如何理解递归？

        在开始学递归时还是需要去分析递归展开细节图的，这个可以让我们理解递归的工作原理，理解为什么递归能解决问题。当我们在逻辑上有了自洽后。就再也不要去管递归展开图，如果一味地去纠结递归展开图，只会让我们越来越晕。

        相反，我们需要从宏观的角度看待递归问题，把递归函数看作一个黑盒并且相信这个黑盒一定能够帮我们完成任务。

4.如何写好递归？

写好递归只需要做好下面这几步：

• 1.找到相同的子问题 --> 解决函数头的设计。
• 2.只关心某个子问题是如何解决的 --> 解决函数体的书写。
• 3.处理递归函数的出口 --> 返回值的确定。

        我们可以知道相同的子问题中的“相同”指的是逻辑相同，而不同的只有操作对象，所以在设计函数头的参数列表时只需要让这些不同的操作对象能够参入即可。

所以我们做这样一个函数头：

void _hanota(vector<int>& A, vector<int>& B, vector<int>& C,int n)；

表示把A柱中n个盘子移动到C柱，B是辅助用的柱子。

        提示：这里大家可能会有一个疑惑，为什么传入的参数是几个盘子，而不是哪几个盘子。其实是因为游戏规则本来就是只能从上往下依次从柱子取盘。 所以知道要取一个盘子也就能确定哪几个盘子，它们是一对一的关系。

单个子问题的解决我放在代码中讲解，如下：

class Solution {
public:void _hanota(vector<int>& A, vector<int>& B, vector<int>& C,int n){if(n==1)//只需要移动一个盘的时候直接操作{C.push_back(A.back());A.pop_back();return;}//先把A中n-1个盘移动到B中_hanota(A,C,B,n-1);//在把剩下一个盘移动到C中C.push_back(A.back());A.pop_back();//最后再把B中的n-1个盘移动到C中_hanota(B,A,C,n-1);}void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {//题目通过的参数列表无法满足我们的需求，重写一个函数来解决。_hanota(A,B,C,A.size());}
};

二、记忆化搜索（记忆递归）

通过下面这个题我会引出记忆化搜索。

以上是一个爬楼梯问题，我们通过找规律来解决问题。

楼顶数：1        2        3        4        5        6

方法数：1        2        3        5        8        13

通过观察发现楼顶数x与方法数F( x )的关系为

出现这样一个递推公式我们第一想到的就是递归来实现。

1.递归代码：

int F(int n)
{if(n<=2) return n;else return F(n-1)+F(n-2);
}

注意：这里为了方便说明问题函数名我直接使用F，这和原题提供的函数名不一样。

下面是对以上代码的递归展开图进行剖析：

红线为递推过程，绿线为回归过程。

接下来是复杂度分析

时间复杂度为O(2^n)，空间复杂度为O(n)

        通过观察我们发现出现很多重复计算的地方（图中画圈颜色相同的地方）如果减少这些重复计算的地方那么效率会提高很多。为了解决这个问题，我们想象一下，把每次计算的数据存起来，下次用到的时候就不用计算，直接返回。而这就是记忆递归。

2.记忆递归

int arr[46]={0};//通过题目确定数据范围
F(int n)
{if(n<=2) return n;if(arr[n]!=0) return arr[n];else return arr[n]=F(n-1)+F(n-2);
}

        创建一个数组并初始值为零，把每次返回的值存在数组里，这样可以避免重复计算，判断a[n]为非0则直接返回。时间复杂度为O(n),空间复杂度为O(n)。

通常能使用记忆递归解决的问题都能转化为动态规划，如下：

3.动态规划

int F(int n){int dp[46]={0};dp[1]=1,dp[2]=2;for(int i=3;i<n+1;i++)dp[i]=dp[i-1]+dp[i-2];return dp[n];
}

        把1到n，每个楼顶对应的方法数存入数组中，用前两个来计算后一个，直到推到n，此方法相比以上方法，减少了递归带来的内存申请，时间复杂度为O(n)，空间复杂度为O(1)。

好题推荐：329. 矩阵中的最长递增路径 - 力扣（LeetCode）

三、回溯

        回溯又叫作“恢复现场”，它是基于递归的一种算法，是为了解决搜索时路径之间的信息互相干扰的问题。如下：

回溯的具体用法，我们来从下面这个题中感受。 

        在做搜索题的时候最重要的莫过于就是决策树的设计。如果决策树做得清晰明了，那么代码也就好写了。

        什么是决策树？在搜索过程中它抽象出来的必定是一棵树形结构，而这棵树是如何展开的，我们在设计展开逻辑的过程，也就是在做一颗决策树。如下：

class Solution {
public:vector<vector<int>> ret;//统计结果vector<int> path;//记录路径vector<vector<int>> subsets(vector<int>& nums){dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){if(pos==nums.size())//即到达叶子节点{ret.push_back(path);return;}//不选该元素直接进入下一元素的选择dfs(nums,pos+1);//选择该元素并进入下一元素的选择path.push_back(nums[pos]);dfs(nums,pos+1);//函数退出之前先把该层的数据清除（回溯）path.pop_back();}
};

其实这里回溯思想就一句代码，即path.pop_back()。回溯就这么简单。

我们看一看没有回溯的决策树：

这里以叶子节点3开始画回归路线，蓝线：回归，红线：递推。

        我们可以看到如果不把[3]这一节点的信息清除的话它会把信息带到上一层，然后一直往下带，每一节点都不恢复现场，就会使每个节点都带上一个信息往回传，导致结果错误。所以回溯算法在很多场景都是至关重要的。

当然决策树并不是唯一的，每个人画的可能都不一样，比如还可以这样：

不同的决策树代码也是不同的，如下：

class Solution
{
public:vector<vector<int>> ret;vector<int> path;vector<vector<int>> subsets(vector<int>& nums){_subsets(nums,0);return ret;}void _subsets(const vector<int>& nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();i++){path.push_back(nums[i]);_subsets(nums,i+1);path.pop_back();//恢复现场}}
};

四、剪枝

        剪枝可以这么理解，如果我们已知某条枝干没有正确答案或某条枝干是错误的，那么我们就不进行搜索，这样可以减少不必要的搜索，提高效率。具体我们可以从题中感受。

这个题放在小学数学就是一个画树状图的题，我们直接开始吧。 

        如上这颗决策树，在一条路径中如果一个元素选过一次，那么下次就不能再选，需要把它剪掉。我们可以使用一个哈希表来记录某个元素是否出现过。但在该过程中同样需要注意“恢复现场”。

class Solution {
public:vector<int> path;vector<vector<int>> ret;int n;vector<vector<int>> permute(vector<int>& nums){n = nums.size();vector<bool> hash(n);dfs(nums,hash);return ret;}void dfs(vector<int>& nums,vector<bool>& hash){if(path.size()==n){ret.push_back(path);return;}for(int i=0;i<n;i++){if(hash[i]) continue;//剪枝hash[i]=true;path.push_back(nums[i]);dfs(nums,hash);hash[i]=false;path.pop_back();}}
};

同样的这里剪枝就一句代码，即 if(hash[i]) continue。剪枝就这么简单。 

五、综合试题 

1.N皇后

首先我们还是一样的试着把决策树画出来，如下： 

这样我们可以知道这个题解题框架。接下来就是处理如何剪枝的问题。

        题目要求一个棋子的横排，竖排，斜对角， 反斜对角都不能有其他棋子，那么这就好办，只需要使用4个哈希表来记录这些位置是否已有棋子，如果有那就不能放，直到遍历完所以格子还是无法将棋子放入，则该条路径行不通。

class Solution {
public:vector<vector<string>> ret;vector<string> path;vector<bool>  row,col,bias1,bias2;vector<vector<string>> solveNQueens(int n){row.resize(n,false),col.resize(n,false);bias1.resize(2*n-1,false),bias2.resize(2*n-1,false);for(int i=0;i<n;i++) path.push_back(string(n,'.'));dfs(0,n);return ret;}void dfs(int pos,int n){if(pos==n){ret.push_back(path);return;}for(int j=0;j<n;j++){//剪枝if(row[pos]||col[j]||bias1[pos+j]||bias2[n-pos+j-1]) continue;row[pos]=col[j]=bias1[pos+j]=bias2[n-pos+j-1]=true;path[pos][j]='Q';dfs(pos+1,n);//恢复现场（回溯）row[pos]=col[j]=bias1[pos+j]=bias2[n-pos+j-1]=false;path[pos][j]='.';}}
};

2.解数独 

        同样我们需要画出决策树，我们可以直接暴力搜索每一个空缺的位置，再在每一个空位暴力枚举每一个数字即可。如下：

        在此过程中我们需要注意剪枝与回溯的问题，为了检查数字的合法性，还需要我们记录每一行，每一列，每个3*3小方格中的某个数字是否出现过。所以需要3个哈希表。

由题可知行数列数都是固定的，为9行9列。

        所以可以用   bool row[9][10]     bool col[9][10]来作为哈希表记录某一行的某个数字是否出现过。

使用bool hash[3][3][10]，来作为哈希表记录某一个3*3宫格的某个数字是否出现过。

代码示例：

class Solution
{
public:bool row[9][10],col[9][10],hash[3][3][10];void solveSudoku(vector<vector<char>>& board){//初始化哈希表for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]=='.') continue;int key=board[i][j]-'0';row[i][key]=col[j][key]=hash[i/3][j/3][key]=true;}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]!='.') continue;for(int key=1;key<=9;key++){if(row[i][key]||col[j][key]||hash[i/3][j/3][key]) continue;//剪枝board[i][j]=key+'0';row[i][key]=col[j][key]=hash[i/3][j/3][key]=true;if(dfs(board)) return true;//剪枝//恢复现场board[i][j]='.';row[i][key]=col[j][key]=hash[i/3][j/3][key]=false;}return false;}}return true;}
};

好题推荐：

​​​​​​39. 组合总和 - 力扣（LeetCode）

22. 括号生成 - 力扣（LeetCode）

1219. 黄金矿工 - 力扣（LeetCode）

77. 组合 - 力扣（LeetCode）