【算法】DFS 系列之 穷举/暴搜/深搜/回溯/剪枝（下篇）
【ps】本篇有 8 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）字母大小写全排列
.1- 题目解析
.2- 代码编写
2）优美的排列
.1- 题目解析
.2- 代码编写
3）N 皇后
.1- 题目解析
.2- 代码编写
4）有效的数独
.1- 题目解析
.2- 代码编写
5）解数独
.1- 题目解析
.2- 代码编写
6）单词搜索
.1- 题目解析
.2- 代码编写
7）黄金矿工
.1- 题目解析
.2- 代码编写
8）不同路径 III
.1- 题目解析
.2- 代码编写
一、算法简介
回溯算法是一种经典的递归算法，通常⽤于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从一个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索，否则，回退到上一个状态，重新做出选择。回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题。
// 回溯算法的模板
void dfs(vector<int>& path, vector<int>& choice, ...)
{
// 满⾜结束条件
if (/* 满⾜结束条件 */)
{
// 将路径添加到结果集中
res.push_back(path);
return;
}
// 遍历所有选择
for (int i = 0; i < choices.size(); i++)
{
// 做出选择
path.push_back(choices[i]);
// 做出当前选择后继续搜索
dfs(path, choices);
// 撤销选择
path.pop_back();
}
}其中， path 表示当前已经做出的选择， choices 表示当前可以做的选择。在回溯算法中，我们需要做出选择，然后递归地调用回溯函数。如果满足结束条件，则将当前路径添加到结果集中。
否则，我们需要撤销选择，回到上一个状态，然后继续搜索其他的选择。回溯算法的时间复杂度通常较高，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较低，因为它只需要维护一个状态树。在实际应用中，回溯算法通常需要通过剪枝等方法进行优化，以减少搜索的次数，从而提高算法的效率。
回溯算法是一种非常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单，但是实现起来需要注意一些细节，比如何做出选择、如何撤销选择等。
二、相关例题
1）字母大小写全排列
784. 字母大小写全排列
.1- 题目解析
本题同样可以通过 DFS 来解决。在遇到数字时，将其直接计入结果即可；在遇到字母时，就要考虑改变其大小写，再计入结果，而由“变”和“不变”就可以画出一棵决策树。
.2- 代码编写
class Solution {
string path;
vector<string> ret;
public:
vector<string> letterCasePermutation(string s) {
dfs(s,0);
return ret;
}
void dfs(string& s,int pos)
{
if(pos==s.length())
{
ret.push_back(path);
return;
}
//不变（数字）
char ch=s[pos];
path.push_back(ch);
dfs(s,pos+1);
path.pop_back();
//变（字符）
if( ch>'9')
{
char tmp=change(ch);
path.push_back(tmp);
dfs(s,pos+1);
path.pop_back();
}
}
char change(char ch)
{
if(ch>='a'&&ch<='z')ch-=32;
else ch+=32;
return ch;
}
};2）优美的排列
526. 优美的排列
.1- 题目解析
可以根据能否被整除，来筛选构成优美排列的数，从而画出决策树。
.2- 代码编写
class Solution {
bool check[16];
int ret;
public:
int countArrangement(int n) {
dfs(1,n);
return ret;
}
void dfs(int pos,int n)
{
if(pos == n+1)//原始数组的下标是从1到n的，pos是从1开始遍历的
{
ret++;//统计优美排列的个数
return;
}
for(int i=1;i<=n;i++)
{
if(!check[i] && (pos%i==0 || i%pos==0))
{
check[i]=true;
dfs(pos+1,n);
check[i]=false;
}
}
}
};3）N 皇后
51. N 皇后
.1- 题目解析
首先，我们在第一行放置第一个皇后，然后遍历棋盘的第二行，在可行的位置放置第二个皇后，然后再遍历第三行，在可行的位置放置第三个皇后，以此类推，直到放置了 n 个皇后为止。
需要用一个数组来记录每一行放置的皇后的列数在每一行中，尝试放置一个皇后，并检查是否会和前面已经放置的皇后冲突。如果没有冲突，我们就继续递归地放置下一行的皇后，直到所有的皇后都放置完毕，然后把这个方案记录下来。
在检查皇后是否冲突时，可以用一个数组来记录每一列是否已经放置了皇后，并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对角线，可以用两个数组来记录从左上角到右下角的每一条对角线上是否已经放置了皇后，以及从右上角到左下角的每一条对角线上是否已经放置了皇后。
对于对角线是否冲突的判断可以通过以下流程解决（根据斜率相等得到 y = x + b 和 y = - x + b）:
- 从左上到右下：相同对角线的行列之差相同。（可能为负数，统一加上 n，y - x + n = b + n）
- 从右上到左下：相同对角线的行列之和相同。（y + x = b）
因此需要创建用于存储解决方案的二维字符串数组 solutions ，用于存储每个皇后的位置的一维整数数组 queens ，以及用于记录每一列和对角线上是否已经有皇后的布尔型数组checkCol、 checkDig1 和 checkDig2。
.2- 代码编写
class Solution {
bool checkCol[10],checkDig1[20],checkDig2[20];
vector<vector<string>> ret;
vector<string> path;
int n;
public:
vector<vector<string>> solveNQueens(int _n) {
n=_n;
path.resize(n);
for(int i=0;i<n;i++)
path[i].append(n,'.');
dfs(0);
return ret;
}
void dfs(int row)
{
if(row==n)
{
ret.push_back(path);
return;
}
for(int col=0;col<n;col++)//尝试在当前行放皇后
{
if(!checkCol[col] && !checkDig1[row-col+n] && !checkDig2[row+col])
{
path[row][col]='Q';
checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=true;
dfs(row+1);
path[row][col]='.';
checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=false;
}
}
}
};4）有效的数独
36. 有效的数独
.1- 题目解析
本题并不是 DFS 的题型，而是哈希的题型，为了方便理解下一道《解数独》的 DFS 剪枝，故列在此。
对于本题，我们可以创建三个数组，标记行、列以及 3*3 小方格中是否出现 1~9 之间的数字，具体方式是，可以使用一个二维数组来记录每个数字在每一行中是否出现，一个二维数组来记录每个数字在每一列中是否出现；对于九宫格，则可以用行和列除以 3 得到的商作为九宫格的坐标，并使用一个三维数组来记录每个数字在每一个九宫格中是否出现。在检查是否存在冲突时，只需检查行、列和九宫格里对应的数字是否已被标记。如果数字至少有一个位置（行、列、九宫格）被标记，则存在冲突，返回 false。
.2- 代码编写
class Solution {
bool row[9][10]; //行中的9个数（下标从1开始映射）
bool col[9][10]; //列中的9个数
bool grid[3][3][10]; //3*3方格中的9个数
public:
bool isValidSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.') //是数字
{
//判断是否有效
int num=board[i][j]-'0';
if(row[i][num] || col[j][num]
|| grid[i/3][j/3][num]) // 行/列/3*3方格出现了，就不是有效的
{
return false;
}
row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;//继续向后查验，但要把当前遍历过的位置设为true
}
}
}
return true;
}
};5）解数独
37. 解数独
.1- 题目解析
要找到一种正确结果，只需遍历整个矩阵，遇到空位置（即 ' . '）则填上合适的数，直到遍历完矩阵并将所有空位置填满。
而判断一个数合不合适，只需像上一道题一样，用三个 bool 数组来标识行、列、3*3 方格中的数是否有重复即可。
特别的，我们将 DFS 的递归函数的返回类型设为 bool，这样，函数在填完一个数进入下一层、又向上返回时，就可以告知当前层，当前层所填的数合不合适，是否要换一个数去填。
.2- 代码编写
class Solution {
bool row[9][10],col[9][10],grid[3][3][10];
public:
void solveSudoku(vector<vector<char>>& board) {
//先遍历矩阵，标识有数的位置
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
int num=board[i][j]-'0';
row[i][num]=col[j][num]=grid[i/3][j/3][num]=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]=='.')
{
for(int num=1;num<=9;num++) //寻找合适的数
{
if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num])
{
//填数
board[i][j]='0'+num;
row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
//遍历下一层
if(dfs(board)) return true;//剪枝，当前填的数是合适的，就不必继续试了，于是向上返回true
//恢复现场
board[i][j]='.';
row[i][num]=col[j][num]=grid[i/3][j/3][num]=false;
}
}
return false;//当前层试了所有的数都不合适，就向上返回false
}
}
}
return true; //都填完了，说明填的都合适
}
};6）单词搜索
79. 单词搜索
.1- 题目解析
将每个位置的元素作为第一个字母，然后向相邻的四个方向进行递归，且不能出现重复用同一个位置的元素。通过深度优先搜索的方式，不断地枚举相邻元素作为下一个字母出现的可能性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。
.2- 代码编写
class Solution {
bool vis[7][7];
int m,n;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
public:
bool exist(vector<vector<char>>& board, string word) {
//遍历矩阵，找到board[i][j]==word[0]的位置
m=board.size(),n=board[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(board[i][j]==word[0])
{
vis[i][j]=true;
if(dfs(board,i,j,word,1))return true;//DFS找word
vis[i][j]=false;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board,int i,int j,string& word ,int pos)
{
if(pos==word.size())
return true;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0 && x<m && y>=0 && y<n
&& !vis[x][y] && board[x][y]==word[pos])
{
vis[x][y]=true;
if(dfs(board,x,y,word,pos+1))return true;//剪枝
vis[x][y]=false;
}
}
return false;
}
};7）黄金矿工
1219. 黄金矿工
.1- 题目解析
枚举矩阵中所有的位置当成起点，来一次深度优先遍历，统计出所有情况下能收集到的黄金数的最大值即可。
.2- 代码编写
class Solution {
bool vis[16][16];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int m, n;
int ret;
public:
int getMaximumGold(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) {
vis[i][j] = true;
dfs(grid, i, j, grid[i][j]);
vis[i][j] = false;
}
}
}
return ret;
}
void dfs(vector<vector<int>>& g, int i, int j, int path) {
ret = max(ret, path);
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y]) {
vis[x][y] = true;
dfs(g, x, y, path + g[x][y]);
vis[x][y] = false;
}
}
}
};8）不同路径 III
980. 不同路径 III
.1- 题目解析
.2- 代码编写
class Solution {
bool vis[21][21];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int ret;
int m,n;
int step;//要走的步数
public:
int uniquePathsIII(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
int bx=0,by=0;//寻找起点
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==0)step++;
else if(grid[i][j]==1)bx=i,by=j;
}
}
step+=2;//计入起点和终点
vis[bx][by]=true;
dfs(grid,bx,by,1);//dfs搜索路径，参数：原始矩阵、起点的坐标、当前已走的步数
return ret;
}
void dfs(vector<vector<int>>& grid,int i,int j,int count)
{
if(grid[i][j]==2){
if(count==step)ret++;
return;
}
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0 && x<m && y>=0 && y<n
&& grid[x][y]!=-1 && !vis[x][y])
{
vis[x][y]=true;
dfs(grid,x,y,count+1);
vis[x][y]=false;
}
}
}
};