递归、搜索、回溯算法

记忆化搜索算法

记忆化搜索是一种将动态规划与递归相结合的算法，它通过记录已解决的子问题的解来避免重复计算，从而提高算法的效率。它主要用于解决具有重叠子问题性质的问题，例如斐波那契数列的计算、最短路径问题等。记忆化搜索的实现通常采用一个查找表（如数组或哈希表）来存储已计算过的子问题的解，当需要求解一个子问题时，先查找表中是否存在该子问题的解，如果存在则直接返回，否则进行计算并将结果存入表中。

记忆化搜索为什么叫记忆化搜索

1. 记忆化：记忆化搜索的核心在于“记忆”，即通过记录已经计算过的子问题的解来避免重复计算。这种记忆机制是通过一个查找表来实现的，每当计算一个子问题的解时，都会将其存储在查找表中。例如，在计算斐波那契数列时，会将每个斐波那契数存储起来，当下次需要计算相同的斐波那契数时，直接从查找表中获取，而不需要重新计算。

2. 搜索：记忆化搜索本质上是一种搜索算法，它通过递归的方式搜索问题的解空间。在搜索过程中，会不断地将问题分解为更小的子问题，并递归地求解这些子问题。例如，在寻找最短路径的问题中，会从起点开始，逐步搜索到各个相邻节点的最短路径，直到找到终点。

记忆化搜索的原理

记忆化搜索的原理可以概括为以下几点：

1. 递归搜索：记忆化搜索采用递归的方式对问题进行搜索，将问题分解为多个子问题，并递归地求解这些子问题。

2. 记忆化存储：在递归搜索的过程中，会将每个已解决的子问题的解存储在一个查找表中。这样，当下次遇到相同的子问题时，可以直接从查找表中获取解，而不需要重新计算。

3. 避免重复计算：通过记忆化存储，记忆化搜索能够有效地避免重复计算相同的子问题，从而大大提高了算法的效率。

记忆化搜索与动态规划的关系

记忆化搜索和动态规划都是用于解决具有重叠子问题性质的问题，它们在原理上是相似的，但实现方式有所不同：

1. 记忆化搜索：记忆化搜索是一种自顶向下的方法，它从问题的原始规模开始，通过递归的方式逐步将问题分解为更小的子问题，并在递归过程中利用记忆化机制存储已解决的子问题的解。

2. 动态规划：动态规划是一种自底向上的方法，它从最小规模的子问题开始，逐步构建更大规模子问题的解，直到求解出原始问题的解。动态规划通常使用一个表格来存储子问题的解，按照一定的顺序填充表格。

记忆化搜索的实现

记忆化搜索的实现通常包括以下几个步骤：

1. 定义递归函数：定义一个递归函数来表示问题的求解过程，该函数的参数通常表示子问题的规模。

2. 创建查找表：创建一个查找表（如数组或哈希表）来存储已解决的子问题的解。

3. 递归基条件：确定递归的基条件，即问题的最小规模的解，可以直接返回而不必进一步递归。

4. 记忆化检查：在递归函数中，首先检查当前子问题的解是否已经存在于查找表中，如果是，则直接返回该解。

5. 递归求解：如果当前子问题的解尚未被计算，则通过递归调用函数来求解子问题，并将结果存储到查找表中。

6. 返回结果：最终，递归函数返回原始问题的解。

记忆化搜索的优点

1. 提高效率：通过记忆化机制，避免了重复计算相同的子问题，从而大大提高了算法的效率。

2. 简化编程：记忆化搜索将动态规划的思路与递归相结合，使得代码更加简洁易懂，降低了编程的复杂度。

3. 灵活应用：记忆化搜索可以应用于多种类型的问题，尤其是那些具有重叠子问题性质的问题。

记忆化搜索的缺点

1. 空间复杂度：记忆化搜索需要额外的空间来存储已解决的子问题的解，因此空间复杂度相对较高。

2. 递归深度：在某些情况下，记忆化搜索的递归深度可能较大，可能导致栈溢出等问题。

记忆化搜索的应用场景

记忆化搜索适用于具有重叠子问题性质的问题，常见的应用场景包括：

1. 斐波那契数列：计算斐波那契数列时，利用记忆化搜索可以避免重复计算相同的斐波那契数。

2. 最短路径问题：在图中寻找两点之间的最短路径时，记忆化搜索可以记录已访问的节点和路径长度，避免重复计算。

3. 动态规划问题：许多动态规划问题，如背包问题、最长公共子序列等，都可以通过记忆化搜索来求解。

实战题目

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

记忆化搜索思路

1. 问题分解：对于矩阵中的每个元素，我们需要找到以该元素为起点的最长递增路径的长度。整个问题可以分解为多个子问题，即从每个元素出发的最长递增路径长度。

2. 递归搜索：对于每个元素，我们可以使用深度优先搜索（DFS）来探索其四个方向的邻居。如果邻居的值大于当前元素的值，则可以继续递归地搜索该邻居，并将路径长度加1。

3. 记忆化存储：为了避免重复计算相同的子问题，我们使用一个二维数组 memo 来记录每个元素作为起点时已经计算过的最长递增路径长度。这样，当再次需要计算该元素的最长路径时，可以直接从 memo 中获取结果，而不需要重新进行递归搜索。

4. 遍历所有元素：遍历矩阵中的每个元素，对于每个元素，如果其对应的 memo 值尚未计算，则进行递归搜索并更新 memo。最终，矩阵中所有元素对应的最长递增路径长度的最大值即为所求。

在矩阵中的最长递增路径问题中，每个元素所对应的最长递增路径是固定不变的。这意味着一旦我们计算出某个元素的最长递增路径长度，这个结果在后续的计算中可以被多次使用。因此，通过记忆化搜索，我们可以将这些结果存储起来，避免重复计算，从而减少时间复杂度。

代码：

class Solution 
{
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        m=matrix.size(),n=matrix[0].size();
        int maxpath=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(memo[i][j]) maxpath=max(maxpath,memo[i][j]);
                else
                    maxpath=max(maxpath,dfs(matrix,i,j));
            }
        }
        return maxpath;
    }

    int dfs(vector<vector<int>>& matrix,int x,int y)
    {
        if(memo[x][y]) return memo[x][y];
        int ret=1;
        for(int i=0;i<4;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx>=0&&newx<m&&newy>=0&&newy<n&&matrix[newx][newy]>matrix[x][y])
                ret=max(ret,dfs(matrix,newx,newy)+1);
        }
        memo[x][y]=ret;
        return ret;
    }
private:
    int memo[201][201];
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    int m,n;
};

题目二：375. 猜数字大小 II - 力扣（LeetCode）

记忆化搜索思路

1. 问题定义：我们需要找到在数字范围 [1, n] 内，确保猜到正确数字所需的最大金额的最小值。这个问题可以分解为多个子问题，即在较小的数字范围内找到最优策略。

2. 记忆化搜索：使用一个二维数组 memo 来存储已经计算过的子问题的结果，避免重复计算。memo[left][right] 表示在数字范围 [left, right] 内，确保猜到正确数字所需的最大金额。

3. 递归函数：定义一个递归函数 dfs(left, right)，它表示在数字范围 [left, right] 内，确保猜到正确数字所需的最大金额。递归函数的逻辑如下：

   • 基本情况：如果 left >= right，说明范围无效或只有一个数字，此时不需要猜测，返回0。

   • 记忆化检查：如果 memo[left][right] 已经被计算过，直接返回该值。

   • 递归计算：对于范围 [left, right] 内的每个可能的猜测点 i，计算在最坏情况下需要的金额，即 max(dfs(left, i-1), dfs(i+1, right)) + i。选择所有可能的 i 中使得这个金额最小的值作为 memo[left][right] 的值。

4. 返回结果：最终，dfs(1, n) 返回在范围 [1, n] 内确保猜到正确数字所需的最大金额的最小值。

代码：

class Solution 
{
public:
    int getMoneyAmount(int n) 
    {
        return dfs(1,n);
    }
    int dfs(int left,int right)
    {
        if(left>=right) return 0;//当left==right时，表明的是猜到了
        if(memo[left][right]) return memo[left][right];
        int ret=INT_MAX;
        for(int i=left;i<=right;i++)
        {
            ret=min(ret,max(dfs(left,i-1),dfs(i+1,right))+i);
        }
        memo[left][right]=ret;
        return ret;
    }
private:
    int memo[201][201];
};

示例解释

假设 n = 3，我们需要找到在最坏情况下所需的最小金额。

• 范围 [1, 3]：

  • 猜测 1：如果对方选择 2 或 3，我们需要继续猜测，最大损失为 1 + dfs(2, 3)。

  • 猜测 2：如果对方选择 1 或 3，我们需要继续猜测，最大损失为 2 + max(dfs(1, 1), dfs(3, 3)) = 2。

  • 猜测 3：如果对方选择 1 或 2，我们需要继续猜测，最大损失为 3 + dfs(1, 2)。

通过递归计算，我们发现选择 2 作为初始猜测点时，最大损失最小，为 2。因此，memo[1][3] = 2。

动态规划思路

1. 问题定义：我们需要找到在数字范围 [1, n] 内，确保猜到正确数字所需的最大金额的最小值。这个问题可以分解为多个子问题，即在较小的数字范围内找到最优策略。

2. 动态规划状态定义：定义 dp[i][j] 表示在数字范围 [i, j] 内，确保猜到正确数字所需的最大金额。我们的目标是求解 dp[1][n]。

3. 状态转移方程：对于每个数字范围 [i, j]，我们需要考虑在该范围内猜测每一个可能的数字 k 作为候选数字。如果猜测 k，则可能的损失为 k 加上在子范围 [i, k-1] 或 [k+1, j] 中继续猜测的最大金额（取决于对方选择的数字在哪一侧）。我们需要在所有可能的 k 中选择一个使得最大损失最小的策略。

4. 初始化和边界条件：当 i >= j 时，不需要猜测，因此 dp[i][j] = 0。对于其他情况，初始值可以设置为一个较大的值（如 j + dp[i][j-1]），以便在后续计算中逐步优化。

5. 填充动态规划表：按照数字范围从小到大的顺序填充动态规划表。对于每个范围 [i, j]，遍历所有可能的猜测点 k，并更新 dp[i][j] 的值。

代码

class Solution 
{
public:
    int getMoneyAmount(int n) 
    {
        vector<vector<int>> dp(n+1,vector<int>(n+1));
        for(int i=n-1;i>=1;i--)
        {
            for(int j=i+1;j<=n;j++)
            {
                //在这段代码中，dp[i][j] 表示在数字范围 [i, j] 内，确保猜到正确数字所需的最大金额。
                //初始化 dp[i][j] = j + dp[i][j-1] 的目的是为后续的动态规划计算提供一个初始的、合理的上界。
                dp[i][j]=j+dp[i][j-1];
                for(int k=i;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j]));
                }
            }
        }
        return dp[1][n];
    }
};

示例解释

假设 n = 3，我们需要找到在最坏情况下所需的最小金额。

• 范围 [1, 3]：

  • 猜测 1：如果对方选择 2 或 3，我们需要继续猜测，最大损失为 1 + dp[2][3]。

  • 猜测 2：如果对方选择 1 或 3，我们需要继续猜测，最大损失为 2 + max(dp[1][1], dp[3][3]) = 2。

  • 猜测 3：如果对方选择 1 或 2，我们需要继续猜测，最大损失为 3 + dp[1][2]。

通过动态规划计算，我们发现选择 2 作为初始猜测点时，最大损失最小，为 2。因此，dp[1][3] = 2。

题目三：300. 最长递增子序列 - 力扣（LeetCode）

记忆化搜索思路

1. 问题定义：我们需要找到数组中最长递增子序列的长度。这个问题可以通过动态规划或记忆化搜索来解决。这里我们使用记忆化搜索的方法。

2. 记忆化搜索：记忆化搜索是一种结合了递归和动态规划思想的算法。它通过记录已解决的子问题的解来避免重复计算，从而提高效率。在这里，我们使用一个数组 memo 来存储从每个位置出发的最长递增子序列的长度。

3. 递归函数：定义一个递归函数 dfs(pos, nums)，它表示从数组的 pos 位置出发，能够形成的最长递增子序列的长度。递归函数的逻辑如下：

   • 基本情况：如果 pos 是数组的最后一个元素，那么以该元素结尾的最长递增子序列的长度为1。

   • 记忆化检查：如果 memo[pos] 已经被计算过，直接返回该值。

   • 递归计算：对于从 pos 位置之后的每个元素，如果该元素大于 nums[pos]，则递归计算从该元素位置出发的最长递增子序列的长度，并更新当前的最大长度。

4. 遍历所有位置：遍历数组中的每个位置，对于每个位置，如果其对应的 memo 值尚未计算，则调用递归函数进行计算。最终，所有位置中的最大值即为数组的最长递增子序列的长度。

代码：

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        n=nums.size();
        int maxpath=1;
        for(int i=0;i<n;i++)
        {
            if(memo[i]) maxpath=max(maxpath,memo[i]);
            else
            {
                maxpath=max(maxpath,dfs(i,nums));
            }
        }
        return maxpath;
    }
    int dfs(int pos,vector<int>& nums)
    {
        if(memo[pos]) return memo[pos];
        int ret=1;
        for(int i=pos;i<n;i++)
        {
            if(nums[i]>nums[pos])
            {
                ret=max(ret,dfs(i,nums)+1);
            }
        }
        memo[pos]=ret;
        return ret;
    }
private:
    int memo[2501];
    int n;
};

示例解释

假设数组为 [10, 9, 2, 5, 3, 7, 101, 18]：

• 从位置0（值为10）出发，后续没有比10大的元素，所以 memo[0] = 1。

• 从位置1（值为9）出发，后续没有比9大的元素，所以 memo[1] = 1。

• 从位置2（值为2）出发，后续有5、3、7、101、18，其中比2大的元素有5、3、7、101、18。递归计算这些位置的最长递增子序列长度：

  • 从位置3（值为5）出发，后续有3、7、101、18，比5大的元素有7、101、18。递归计算这些位置的最长递增子序列长度：

    • 从位置4（值为3）出发，后续有7、101、18，比3大的元素有7、101、18。递归计算这些位置的最长递增子序列长度：

      • 从位置5（值为7）出发，后续有101、18，比7大的元素有101、18。递归计算这些位置的最长递增子序列长度：

        • 从位置6（值为101）出发，后续没有比101大的元素，所以 memo[6] = 1。

        • 从位置7（值为18）出发，后续没有比18大的元素，所以 memo[7] = 1。

      • 因此，memo[5] = max(1 + 1, 1 + 1) = 2。

    • 因此，memo[4] = max(1 + 2, 1 + 1) = 3。

  • 因此，memo[3] = max(1 + 3, 1 + 1, 1 + 2) = 4。

• 因此，memo[2] = max(1 + 4, 1 + 3, 1 + 2) = 5。

最终，maxpath 的值为5，即最长递增子序列的长度为5。

动态规划思路

1. 问题定义：我们需要找到数组中最长递增子序列的长度。这个问题可以通过动态规划来解决。

2. 动态规划状态定义：定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。初始时，每个元素的 dp[i] 都初始化为1，因为每个元素本身至少可以构成长度为1的递增子序列。

3. 状态转移方程：对于每个元素 nums[i]，我们需要检查其前面的所有元素 nums[j]（其中 j < i）。如果 nums[j] < nums[i]，则说明可以将 nums[i] 添加到以 nums[j] 结尾的递增子序列后面，形成一个更长的递增子序列。此时，dp[i] 的值可以更新为 dp[j] + 1。我们需要在所有可能的 j 中选择最大的 dp[j] + 1 作为 dp[i] 的值。

4. 遍历数组：从左到右遍历数组，对于每个元素，计算其对应的 dp[i] 值，并维护一个全局最大值变量 maxpath，用于记录整个数组中最长递增子序列的长度。

代码：

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> dp(n,1);
        int maxpath=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i]) dp[i]=max(dp[i],dp[j]+1);
            }
            maxpath=max(dp[i],maxpath);
        }
        return maxpath;
    }
};

示例解释

假设数组为 [10, 9, 2, 5, 3, 7, 101, 18]：

• 初始化 dp 数组为 [1, 1, 1, 1, 1, 1, 1, 1]，maxpath 为1。

• 处理 i = 1（值为9）：

  • 检查 j = 0（值为10），9不大于10，不更新 dp[1]。

  • dp[1] 仍为1，maxpath 仍为1。

• 处理 i = 2（值为2）：

  • 检查 j = 0 和 j = 1，2不大于10和9，不更新 dp[2]。

  • dp[2] 仍为1，maxpath 仍为1。

• 处理 i = 3（值为5）：

  • 检查 j = 0、j = 1 和 j = 2：

    • nums[2] = 2 < 5，所以 dp[3] = max(1, dp[2] + 1) = 2。

  • maxpath 更新为2。

• 处理 i = 4（值为3）：

  • 检查 j = 0、j = 1、j = 2 和 j = 3：

    • nums[2] = 2 < 3，所以 dp[4] = max(1, dp[2] + 1) = 2。

  • maxpath 仍为2。

• 处理 i = 5（值为7）：

  • 检查 j = 0 到 j = 4：

    • nums[2] = 2 < 7，dp[5] = max(1, dp[2] + 1) = 2。

    • nums[3] = 5 < 7，dp[5] = max(2, dp[3] + 1) = 3。

    • nums[4] = 3 < 7，dp[5] = max(3, dp[4] + 1) = 3。

  • maxpath 更新为3。

• 处理 i = 6（值为101）：

  • 检查 j = 0 到 j = 5：

    • 所有前面的元素都小于101，所以 dp[6] = max(1, dp[j] + 1)，其中 j 从0到5。

    • 最终 dp[6] = 4（从 j = 5 得到 dp[5] + 1 = 3 + 1 = 4）。

  • maxpath 更新为4。

• 处理 i = 7（值为18）：

  • 检查 j = 0 到 j = 6：

    • nums[5] = 7 < 18，所以 dp[7] = max(1, dp[5] + 1) = 4。

    • nums[6] = 101 不小于18，不更新。

  • maxpath 仍为4。

最终，maxpath 的值为4，即最长递增子序列的长度为4。

DFS算法

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法，其基本思想是尽可能深地搜索树或图的分支，直到无法继续为止，然后回溯并探索其他路径。

基本原理

• 起始节点：从一个指定的起始节点开始，将其标记为已访问。

• 深入搜索：沿着一条路径尽可能深地搜索，直到无法继续前进，即遇到叶子节点（无子节点的节点）或所有邻接节点都已被访问过。

• 回溯：当无法继续深入时，回溯到上一个节点，继续探索该节点的其他未被访问的邻接节点。

• 重复过程：重复上述步骤，直到所有节点都被访问过为止。

操作步骤

• 递归实现：

  1. 访问当前节点，并标记为已访问。

  2. 遍历当前节点的所有邻接节点，对于每个未被访问的邻接节点，递归执行深度优先搜索。

• 迭代实现：

  1. 创建一个栈，用于存储待访问的节点。

  2. 将起始节点入栈，并标记为已访问。

  3. 循环执行以下操作，直到栈为空： a. 出栈一个节点，并访问该节点。 b. 将该节点的所有未被访问的邻接节点依次入栈，并标记为已访问。

实战题目

题目一：529. 扫雷游戏 - 力扣（LeetCode）

详细解题思路

1. 问题分析：

   • 游戏板由字符数组表示，其中 'M' 表示未触发的地雷，'X' 表示触发的地雷，'B' 表示空地，数字字符表示周围地雷的数量。

   • 玩家点击一个位置 (click[0], click[1])，需要根据该位置的类型进行不同的处理。

2. 算法选择：

   • 使用深度优先搜索（DFS）来处理空地的递归揭示。当点击一个空地时，需要检查其周围是否有地雷。如果没有地雷，则继续递归揭示周围的空地；如果有地雷，则标记该位置为地雷数量。

3. 具体步骤：

   • 检查点击位置是否为地雷：如果是地雷，直接将其标记为触发状态 'X' 并返回。

   • 初始化变量：获取游戏板的行数和列数，初始化方向数组和访问标记数组。

   • DFS 函数：

     • 标记访问：将当前点击位置标记为已访问。

     • 统计周围地雷数量：遍历当前点击位置的八个方向，统计周围地雷的数量。

     • 处理当前点击位置：

       • 如果周围有地雷，将当前点击位置标记为地雷数量。

       • 如果周围没有地雷，将当前点击位置标记为 'B'，并递归揭示其周围的空地。

   • 递归终止条件：当点击位置超出游戏板范围、已访问过或不是空地时，终止递归。

4. 代码实现：

   • 主函数：处理点击事件，判断点击位置是否为地雷，如果不是地雷则调用 DFS 函数。

   • DFS 函数：递归地处理空地的揭示逻辑。

代码：

class Solution 
{
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
    {
        if(board[click[0]][click[1]]=='M')
        {
            board[click[0]][click[1]]='X';
            return board;
        }
        m=board.size(),n=board[0].size();
        dfs(board,click[0],click[1]);
        return board;
    }
    void dfs(vector<vector<char>>& board,int x,int y)
    {
        isvisited[x][y]=true;
        int count=0;
        for(int i=0;i<8;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx>=0&&newx<m&&newy>=0&&newy<n&&board[newx][newy]=='M') count++;
        }
        if(count) 
        {
            board[x][y]='0'+count;
            return;
        }

        board[x][y]='B';
        for(int i=0;i<8;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx>=0&&newx<m&&newy>=0&&newy<n&&isvisited[newx][newy]==false&&board[newx][newy]=='E')
            {
                dfs(board,newx,newy);
            }
        }
    }
private:
    int dx[8]={0,0,1,-1,-1,1,-1,1};
    int dy[8]={1,-1,0,0,-1,-1,1,1}; 
    bool isvisited[51][51];
    int m,n;
};

题目二：417. 太平洋大西洋水流问题 - 力扣（LeetCode）

详细解题思路一

问题分析：

1. 问题理解：每个位置的水流可以向四个方向（上、下、左、右）流动，且只能从高处流向低处或平地处。需要找到所有可以同时流向太平洋和大西洋的位置。

2. 关键点：从边界开始逆流而上，使用深度优先搜索（DFS）标记所有能流向太平洋和大西洋的区域，然后找出两者的交集。

算法选择：

• 深度优先搜索（DFS）：从边界开始，逆着水流方向（即从低到高）进行搜索，标记所有可以到达的位置。这样可以避免重复计算和复杂的动态规划状态转移。

代码实现：

1. 初始化：

   • 获取矩阵的行数 m 和列数 n。

   • 创建两个二维布尔数组 recordpo 和 recordao，分别记录可以流向太平洋和大西洋的位置。

2. DFS 遍历：

   • 从太平洋的边界（左上角）开始，使用 DFS 标记所有可以流向太平洋的位置。

   • 从大西洋的边界（右下角）开始，使用 DFS 标记所有可以流向大西洋的位置。

3. 结果收集：

   • 遍历整个矩阵，找出同时被 recordpo 和 recordao 标记为 true 的位置，这些位置即为所求。

代码：

class Solution 
{
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        vector<vector<int>> result;
        m=heights.size(),n=heights[0].size();
         // 初始化记录数组
        vector<vector<bool>> recordpo(m, vector<bool>(n, false));
        vector<vector<bool>> recordao(m, vector<bool>(n, false));
        dfs(0,0,heights,0,0,recordpo);
        dfs(m-1,n-1,heights,m-1,n-1,recordao);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(recordao[i][j]&&recordpo[i][j]) result.push_back({i,j});
            }
        }
        return result;
    }
    void dfs(int x,int y,vector<vector<int>>& heights,int borderx,int bordery,vector<vector<bool>>& record)
    {
        record[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx>=0&&newx<m&&newy>=0&&newy<n&&record[newx][newy]==false&&
            (heights[newx][newy]>=heights[x][y]||newx==borderx||newy==bordery))
            {
                dfs(newx,newy,heights,borderx,bordery,record);
            }
        }
    }
private:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0}; 
    int m,n;
};

详细解题思路二

问题分析

1. 问题理解：需要找到所有被 'X' 包围的 'O' 并将其转换为 'X'，而位于边界上的 'O' 不会被包围。因此，首先需要确定哪些 'O' 是与边界相连的，这些 'O' 不会被转换。

2. 关键点：使用深度优先搜索（DFS）从边界上的 'O' 开始标记所有与之相连的 'O'，这些 'O' 不会被转换。然后遍历整个矩阵，将未被标记的 'O' 转换为 'X'。

算法选择

• 深度优先搜索（DFS）：从边界上的 'O' 开始，标记所有与之相连的 'O'。这样可以确保不会错误地将这些 'O' 转换为 'X'。

代码逻辑

1. 初始化：

   • 获取矩阵的行数 m 和列数 n。

   • 创建一个二维布尔数组 isused，用于标记是否访问过某个位置。

2. 标记边界上的 'O' 及其相连区域：

   • 遍历矩阵的边界（第一列、最后一列、第一行、最后一行），找到 'O' 并使用 DFS 标记所有与之相连的 'O'。将这些 'O' 暂时标记为 'K'，以避免后续被转换。

3. 处理内部的 'O'：

   • 遍历整个矩阵，对于未被标记且为 'O' 的位置，使用 DFS 将其转换为 'X'。

4. 恢复标记的 'K' 为 'O'：

   • 遍历整个矩阵，将所有标记为 'K' 的位置恢复为 'O'。

代码：

class Solution 
{
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m,n;
    vector<vector<bool>> isused;
public:
    void solve(vector<vector<char>>& board) 
    {
        m=board.size(),n=board[0].size();
        isused=vector<vector<bool>>(m,vector<bool>(n,false));

        for(size_t i=0;i<m;i++)
        {
            if(isused[i][0]==false&&board[i][0]=='O') solvedfs(board,i,0,'K');
            if(isused[i][n-1]==false&&board[i][n-1]=='O') solvedfs(board,i,n-1,'K');
        }

        for(size_t j=0;j<n;j++)
        {
            if(isused[0][j]==false&&board[0][j]=='O') solvedfs(board,0,j,'K');
            if(isused[m-1][j]==false&&board[m-1][j]=='O') solvedfs(board,m-1,j,'K');
        }

        for(size_t i=0;i<m;i++)
        {
            for(size_t j=0;j<n;j++)
            {
                if(isused[i][j]==false&&board[i][j]=='O')
                {
                    solvedfs(board,i,j,'X');
                }
            }
        }


        for(size_t i=0;i<m;i++)
        {
            for(size_t j=0;j<n;j++)
            {
                if(board[i][j]=='K')
                {
                    board[i][j]='O';
                }
            }
        }
    }

    void solvedfs(vector<vector<char>>& board,int x,int y,char tmp)
    {
        board[x][y]=tmp;
        isused[x][y]=true;

        for(size_t i=0;i<4;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx>=0&&newx<m&&newy>=0&&newy<n&&isused[newx][newy]==false&&board[newx][newy]=='O')
            {
                solvedfs(board,newx,newy,tmp);
            }
        }
    }
};

回溯算法

回溯算法是一种通过穷举所有可能的解来求解问题的方法，其核心思想是从问题的初始状态出发，逐步地尝试不同的选择，当发现某个选择不满足条件时，立即返回上一步进行其他选择，直到找到满足条件的解或所有可能的解都被尝试过。

基本思想

回溯算法的基本思想包括以下几点：

1. 逐步构建解：从一个初始状态出发，逐步遍历，构建潜在的解决方案。

2. 检查约束条件：在遍历过程中，检查当前解是否满足问题的约束条件。如果不满足，则立即回退。

3. 回溯机制：如果所有可能的选择都尝试过且未找到有效解，则回退到上一步继续尝试其他可能性。

4. 剪枝：在构建解的过程中，通过提前判断某些路径是否可行，从而减少不必要的计算。

实现步骤

回溯算法的实现通常包括以下步骤：

1. 选择路径：在当前步骤选择一个可能的选择。

2. 剪枝判断：检查当前选择是否满足问题的约束条件。如果不满足，则放弃当前选择（即剪枝）。

3. 递归处理：若当前选择满足条件，则继续递归处理下一个步骤。

4. 回溯：若通过当前选择不能得到解，撤销选择并返回上一步，尝试其他选择。

特点

回溯算法具有以下特点：

1. 系统性：通过深度优先搜索系统地遍历解空间树，确保不会遗漏任何可能的解。

2. 剪枝：在搜索过程中，如果发现某个节点的部分解不满足约束条件，算法会立即停止对该节点的搜索，从而减少不必要的计算。

3. 递归性：通常通过递归实现，代码简洁且易于理解。

4. 可回溯性：在进行选择时有可回退的性质，即当发现某个选择不满足条件时可以返回上一步进行其他选择，以便寻找其他可能的解。

实战题目

题目一：526. 优美的排列 - 力扣（LeetCode）

详细解题思路

1. 问题分析

我们需要构造一个排列，使得每个位置上的数字满足上述两个条件之一。这个问题可以通过回溯算法来解决，因为我们需要尝试所有可能的排列，并统计符合条件的排列数。

2. 回溯算法

回溯算法是一种通过递归尝试所有可能的解，并在发现当前路径无法得到解时回溯到上一步继续尝试的算法。在这个问题中，我们可以通过递归地尝试将每个未使用的数字放在当前的位置上，并检查是否满足条件。

3. 状态表示

使用一个布尔数组 isvisited 来记录哪些数字已经被使用过。数组的索引表示数字，值为 true 表示该数字已被使用，false 表示未被使用。

4. 递归函数设计

递归函数 dfs 的参数包括：

• isvisited：记录哪些数字已被使用。

• pos：当前尝试填充的位置（从 1 到 n）。

• end：目标排列的长度（即 n）。

递归函数的逻辑如下：

• 如果 pos 超过 end，说明已经构造了一个完整的排列，计数器 count 增加 1。

• 否则，遍历所有未被使用的数字，检查是否满足条件（即数字是位置的倍数，或者位置是数字的倍数）。如果满足条件，则标记该数字为已使用，并递归调用 dfs 处理下一个位置。递归返回后，回溯（即取消标记该数字为已使用），继续尝试其他数字。

5. 剪枝

在遍历数字时，只尝试未被使用的数字，并且只在满足条件时进行递归调用，这样可以减少不必要的递归调用，提高效率。

代码：

class Solution 
{
public:
    int countArrangement(int n) 
    {
        vector<bool> isvisited(n+1,false);
        dfs(isvisited,1,n);
        return count;
    }
    void dfs(vector<bool>& isvisited,int pos,int end)
    {
        if(pos>end)
        {
            count++;
            return;
        }
        for(int i=1;i<=end;i++)
        {
            if(isvisited[i]==false&&(i%pos==0||pos%i==0))
            {
                isvisited[i]=true;
                dfs(isvisited,pos+1,end);
                isvisited[i]=false;
            }
        }
    }
private:
    int count=0;
};

题目二：784. 字母大小写全排列 - 力扣（LeetCode）

详细解题思路

1. 问题分析

我们需要生成一个字符串的所有可能的字母大小写排列。字符串中可能包含数字，数字在排列中保持不变。对于每个字母，我们可以选择将其转换为大写或小写，因此每个字母都有两种可能性。最终的排列数是 2^k，其中 k 是字符串中字母的数量。

2. 深度优先搜索（DFS）

这个问题可以通过深度优先搜索（DFS）来解决。DFS 是一种递归算法，用于遍历所有可能的路径。在这个问题中，每个位置的字符（如果是字母）有两种选择（大写或小写），我们需要递归地尝试所有可能的组合。

3. 状态表示

• path：当前构造的排列路径。

• pos：当前处理的字符串位置。

• allpath：存储所有生成的排列结果。

4. 递归函数设计

递归函数 dfs 的参数包括：

• s：原始字符串。

• path：当前构造的排列路径。

• pos：当前处理的字符串位置。

• end：字符串的长度。

递归函数的逻辑如下：

• 如果 pos 等于 end，说明已经处理完所有字符，将当前路径加入结果列表。

• 否则，检查当前字符是否是数字：

  • 如果是数字，直接加入路径，并递归处理下一个位置。

  • 如果是字母，尝试两种情况：原字母和转换大小写后的字母，分别递归处理下一个位置。

5. 剪枝 

在处理字母时，直接跳过数字，只对字母进行大小写转换，这样可以减少不必要的递归调用。

代码：

class Solution 
{
public:
    vector<string> letterCasePermutation(string s) 
    {
        n=s.size();
        string path;
        dfs(s,path,0,n);
        return allpath;
    }
    void dfs(string& s,string& path,int pos, int end)
    {
        if(pos==end)
        {
            allpath.push_back(path);
            return;
        }
        if(s[pos]>='0'&&s[pos]<='9') 
        {
            path.push_back(s[pos]);
            dfs(s,path,pos+1,n);
            path.pop_back();
        }
        else
        {
            path.push_back(s[pos]);
            dfs(s,path,pos+1,n);
            path.pop_back();
            path.push_back(change(s[pos]));
            dfs(s,path,pos+1,n);
            path.pop_back();
        }
    }
private:
    char change(char ret)
    {
        if(ret>='a'&&ret<='z')
        {
            return ret+('A'-'a');
        }
        return ret+('a'-'A');
    }
    vector<string> allpath;
    int n;
};

题目三：37. 解数独 - 力扣（LeetCode）

详细解题思路

1. 初始化标记数组

在开始求解之前，首先遍历整个数独棋盘，记录每一行、每一列以及每个3x3宫格中已经存在的数字。这些信息存储在三个二维数组中：

• across：记录某一行中已经存在的数字。

• vertical：记录某一列中已经存在的数字。

• matrix：记录某个3x3宫格中已经存在的数字。

2. 深度优先搜索（DFS）

DFS函数是求解数独的核心部分。它的目标是找到一个满足所有数独规则的解。具体步骤如下：

        (1) 遍历棋盘

        从左上角开始，逐行逐列检查每个格子。如果格子已经是数字（非.），则跳过；如果格子是.，则尝试填入一个数字。

        (2) 尝试填入数字

        对于空格子（.），尝试填入1到9的数字。在填入之前，需要检查该数字是否已经在当前行、当前列或当前3x3宫格中出现过。如果未出现过，则可以填入该数字。

        (3) 更新标记数组

        一旦填入一个数字，需要更新对应的标记数组，表示该数字已经在对应的行、列和宫格中出现。

        (4) 递归调用DFS

        在填入一个数字后，递归调用DFS函数继续处理下一个空格子。如果递归调用返回true，说明已经找到解，直接返回；否则，需要回溯。

        (5) 回溯

        如果填入某个数字后无法找到解，则需要撤销填入的操作，将该格子重新置为.，并恢复标记数组的状态，以便尝试下一个可能的数字。

3. 回溯算法的关键点

• 剪枝：通过标记数组提前排除不可能的数字，减少尝试的次数。

• 递归终止条件：当遍历完整个棋盘且没有空格子时，说明已经找到解，返回true。

• 回溯操作：在尝试填入一个数字后，如果后续步骤无法找到解，则需要撤销填入，恢复状态，尝试下一个数字。

代码：

class Solution 
{
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]!='.')
                {
                    across[i][board[i][j]-'0']=true;
                    vertical[j][board[i][j]-'0']=true;
                    matrix[(i/3)*3+j/3][board[i][j]-'0']=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 k=1;k<=9;k++)
                    {
                        if(across[i][k]==false&&vertical[j][k]==false&&matrix[(i/3)*3+j/3][k]==false)
                        {
                            board[i][j]='0'+k;
                            across[i][k]=vertical[j][k]=matrix[(i / 3) * 3 + j / 3][k]=true;
                            if(dfs(board)==true) return true;
                            board[i][j]='.';
                            across[i][k]=vertical[j][k]=matrix[(i / 3) * 3 + j / 3][k]=false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
private:
    bool across[9][10];
    bool vertical[9][10];
    bool matrix[9][10];
};