算法妙妙屋-------2..回溯的奇妙律动

回溯算法是一种用于系统性地搜索和解决问题的算法，它以深度优先搜索（DFS）为基础，用来探索所有可能的解决方案。通过递归地尝试候选解并在必要时回退（即“回溯”），它能够高效地解决许多涉及组合、排列和分割问题的场景。

在这里插入图片描述

核心思想

递归：回溯算法通常以递归方式实现，每次深入问题的一个分支。
状态空间树：将问题抽象成一个树形结构，每个节点代表一个部分解或状态。
剪枝：在探索过程中，提前排除不可能的解以减少计算量。
回退：当某一条路径无法产生有效解时，返回上一步并尝试其他路径。

典型应用

排列与组合问题：如求全排列、子集生成。
路径搜索问题：如迷宫问题、数独求解。
优化问题：如0/1背包问题。
约束满足问题：如八皇后问题、图着色问题。

算法流程

选择：选择一个可能的路径或解分支。
约束检查：判断当前选择是否满足问题的约束条件。
递归搜索：继续深入探索下一个状态。
回溯：若当前选择无效，则返回上一步重新选择。

优势与不足

优势：实现简单，适合解决所有可能解的穷举问题。
不足：在问题规模较大时，计算复杂度可能过高，需要结合剪枝优化。

简单示例（伪代码）：

def backtrack(path, options):if 满足结束条件:记录结果returnfor option in options:做选择backtrack(新的路径, 剩余选择)撤销选择

通过以上步骤，回溯算法能够在复杂解空间中寻找问题的最优解或所有可能解。

1.单词搜索

题目链接：单词搜索

在这里插入图片描述
解题思路：

1.将整个数组向外扩充一环（避免讨论边缘问题）
2.进行深度优先搜索

class Solution {
public:bool dfs(vector<vector<char>>& square, string word,int position,int i,int j,vector<vector<bool>>& check)
{if(position==word.size())return true;if(square[i][j+1]==word[position]&&!check[i][j+1])//判断右{check[i][j+1]=true;if(dfs(square, word,position+1,i,j+1,check)){return true;//这种类型的题目需要return，因为只需查找一个即可满足题意。}else{check[i][j+1]=false;}}if(square[i][j-1]==word[position]&&!check[i][j-1])//判断左{check[i][j-1]=true;if(dfs(square, word,position+1,i,j-1,check)){return true;}else{check[i][j-1]=false;}}if(square[i+1][j]==word[position]&&!check[i+1][j])//判断下{check[i+1][j]=true;if(dfs(square, word,position+1,i+1,j,check)){return true;}else{check[i+1][j]=false;}}if(square[i-1][j]==word[position]&&!check[i-1][j])//判断上{check[i-1][j]=true;if(dfs(square, word,position+1,i-1,j,check)){return true;}else{check[i-1][j]=false;}}return false;
}bool exist(vector<vector<char>>& board, string word) {int row=board.size();int line=board[0].size();vector<vector<bool>>check(row+2,vector<bool>(line+2,false));//初始化二维数组vector<vector<char>>square(row+2,vector<char>(line+2,'0'));for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){square[i][j]=board[i-1][j-1];}}for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){if(square[i][j]==word[0]){check[i][j]=true;if(dfs(square,word,1,i,j,check)){return true;}check[i][j]=false;  //恢复现场}}}return false;}
};

2.黄金矿工

题目链接：黄金矿工

在这里插入图片描述
解题思路：

枚举矩阵中所有的位置当成起点，来⼀次深度优先遍历，统计出所有情况下能收集到的⻩⾦数的最⼤值即可。

class Solution {
public:int maximum=0;int sum=0;void dfs(vector<vector<int>>& square,int i,int j,vector<vector<bool>>& check)//不需要return，因为要全部遍历一遍才能找到最优解{if(square[i][j+1]!=0&&!check[i][j+1])//判断右{check[i][j+1]=true;sum+=square[i][j+1];dfs(square,i,j+1,check);check[i][j+1]=false;sum-=square[i][j+1];}if(square[i][j-1]!=0&&!check[i][j-1])//判断左{check[i][j-1]=true;sum+=square[i][j-1];dfs(square,i,j-1,check);check[i][j-1]=false;sum-=square[i][j-1];}if(square[i+1][j]!=0&&!check[i+1][j])//判断下{check[i+1][j]=true;sum+=square[i+1][j];dfs(square,i+1,j,check);check[i+1][j]=false;sum-=square[i+1][j];}if(square[i-1][j]!=0&&!check[i-1][j])//判断上{check[i-1][j]=true;sum+=square[i-1][j];dfs(square,i-1,j,check);check[i-1][j]=false;sum-=square[i-1][j];}maximum=max(sum,maximum);//每一次dfs走到底的时候就进行比较，保留最大值}int getMaximumGold(vector<vector<int>>& grid) {int row=grid.size();int line=grid[0].size();vector<vector<bool>>check(row+2,vector<bool>(line+2,false));//初始化二维数组vector<vector<int>>square(row+2,vector<int>(line+2,0));for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){square[i][j]=grid[i-1][j-1];}}for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){if(square[i][j]!=0){check[i][j]=true;sum+=square[i][j];dfs(square,i,j,check);check[i][j]=false;sum=0;//更换起点，路径长度要归零。}}}return maximum;}
};

注意：黄金矿工和单词搜索不一样，单词搜索只需要找到一个满足题意的路径即可（即找到之后剩下的无需遍历，需要return 返回）而黄金矿工需要遍历所有路径来找到最优解，无需return。

3.不同路径III

题目链接：不同路径III

在这里插入图片描述
解题思路：

递归结束条件：当前位置的元素值为2，若此时可⾛的位置数量num的值为0，则cnt的值加⼀；

class Solution {
public:int num=0;
int row=0;
int line=0;bool judge(vector<vector<bool>>&check)
{for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){  if(check[i][j]==false)//有格子没走过return false;}}return true;//所有格子都走过
}void dfs(vector<vector<int>>& square,int i,int j,vector<vector<bool>>&check)
{if(square[i][j]==2)  //走到终点{if(judge(check)){num++;  //路径数量++；}}if((square[i][j+1]==0||square[i][j+1]==2)&&!check[i][j+1])//判断右{check[i][j+1]=true;dfs(square,i,j+1,check);check[i][j+1]=false;//恢复现场}if((square[i][j-1]==0||square[i][j-1]==2)&&!check[i][j-1])//判断左{check[i][j-1]=true;dfs(square,i,j-1,check);check[i][j-1]=false;//恢复现场}if((square[i+1][j]==0||square[i+1][j]==2)&&!check[i+1][j])//判断下{check[i+1][j]=true;dfs(square,i+1,j,check);check[i+1][j]=false;//恢复现场}if((square[i-1][j]==0||square[i-1][j]==2)&&!check[i-1][j])判断上{check[i-1][j]=true;dfs(square,i-1,j,check);check[i-1][j]=false;//恢复现场}}int uniquePathsIII(vector<vector<int>>& grid) {row=grid.size();line=grid[0].size();int position_row=0;int position_line=0;vector<vector<bool>>check(row+2,vector<bool>(line+2,false));vector<vector<int>>square(row+2,vector<int>(line+2,3));for(int i=1;i<row+1;i++){for(int j=1;j<line+1;j++){square[i][j]=grid[i-1][j-1];if(square[i][j]==1||square[i][j]==-1){if(square[i][j]==1){position_row=i;//找入口的行position_line=j;//找入口的列}check[i][j]=true; //}}}dfs(square,position_row, position_line,check);return num;}
};