这里面用了一些stl的东西，如果看见vector<T>这种，把他当一维数组就行，如果看见了vector<vector<T>> 把他当做一个二维数组即可。如果实在看不懂一些代码的话，就点击链接进入题解有其他语言版本的题解，找到自己熟悉的语言题解。然后我给的代码没有看见主函数的话，就把第一个函数当做主函数就行。

以下题目均从力扣中获取力扣

1.初识递归

递归的意思是程序在运行中的自我调用，这什么意思呢？举个例子：在《瑞克和莫提》这个动漫中有一集提到，瑞克和莫提用进入梦境的工具进入莫提数学老师的梦境来暗示数学老师要给莫提的数学成绩打满分，他们进入老师梦境之后又继续进入了梦境中其他人的梦境，这样持续的套娃进入，到最后原路返回，但是每一次返回的结果都会影响进去时的状态。这例子可能有点牵强，那我们来一些实例来看看。

首先我们来实现一个阶乘的递归函数


#include <iostream>
using namespace std;
 
int factorial(int );
int main()
{
    cout << factorial(6);
    return 0;
}
 
int factorial(int n)
{
    if (n == 1) return 1;           // 终止条件
    return n * factorial(n - 1);    // 递归调用
}

在我们求解factorial(6)的时候我们可以转变为6 * factorial(5)，然后factorial(5) = 5 * factorial(4)，以此类推我们就能的到最终的答案，具体是 6 * 5 * 4 * 3 * 2 * factorial(1)，因为当n == 1的时候终止了递归也就是递归结束了factorial(1) = 1，看上图的变化应该可以很快的理解。

那么现在问题来了，我们什么时候要考虑去用递归解决问题？当我们知道了要用递归解决问题的时候，如何去写一个递归函数？

首先解决第一个问题，我们用代码来解释问题，我们上面写的代码我们发现如果函数递归调用的话，那么每一个函数的步骤都是一样的，以上面举例，都是先进行一个if判断，然后选择是否进行下一步递归，我们由此可以发现，问题满足递归的第一个条件就是子问题要和父问题的操作是一样的，第二条件我们可以这样想，如果把问题举例成领导分配任务，省长给市长，市长给县长，县长给镇长，镇长给村长，村长给村民，是不是有一个终止的点，不可能一直分配下去吧，总得有个结束的地方，那么这就是第二条件，不能无休止递归下去，要有一个出口可以终止递归。总结一下，1.子问题要跟父问题的操作一样。2.要有一个出口可以终止递归。

那么来解决第二个问题，如何写一个递归函数。其实说实话我也不知道该怎么写，应该注意上面两个条件就行，熟能生巧吧。

2.递归的简单例子

那么就来几个例子去练练手吧。

509. 斐波那契数（链接力扣）

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.其实就是当n>1时，你当前值等于前面两项之和。

这个题用递归的话大概率会超时，但是我们还是给出递归代码


int dfs(int n)
{
    if(n == 0 || n == 1) return n;
    // if(n == 0) return 0;
    // if(n == 1) return 1;
    // 上面两行代码跟第一行同样效果
    return dfs(n - 1) + dfs(n - 2);
}

拿到这个题我们可以先举例，也就是穷举，f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5, f(6) = 8, f(7) = 13，ok我们先举例这么多，我们看题意得知当前项等于前两项之和，跟我们举例出来的看见的规律是一致的，那么回到使用递归两个条件那，我们可以得知在这里子问题和父问题得操作是一样的，并且有递归终止条件n < 2 时就会停止。那我们写这个代码就注意两点，第一代码的终止条件是什么，第二相同的操作是什么。那么我们再给出另外一种解法，这个解法叫动态规划，这个暂时不在此贴讨论，以后有时间会出一期动态规划的一些问题详解。


// 数组版本
 
int fib(int n)
{
    if (n == 0) return 0;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}
 
 
 
// 空间优化版本
 
int fib(int n)
{
    if (n < 2) return n;
    int pre = 0, cur = 1;           // pre相当于dp[i - 2]，cur相当于dp[i - 1]
    for (int i = 2; i <= n; ++i)
    {
        int temp = cur;
        cur = cur + pre;
        pre = temp;
    }
    return cur;
}

小牛问题：

某农场有一头刚出生的小奶牛，从第四个年头开始每年生一头母牛。之后的每一年大奶牛都会生一只小奶牛，而每过四年小奶牛就会长成大奶牛，长成大奶牛后又可以生小奶牛。请问 N 年后，此农场一共有多少头牛？（这题没在力扣中找到）

先理解题目意思，其实这个题就是小牛要三年时间长大，然后第四年就可以生崽了。来，我们还是先枚举

图片是我从别人那偷过来的，我们先不管递不递归的，我们从规律就能发现当你的n > 3 的时候就有了上述那个公式 cow(n) = cow(n - 1) + cow(n - 3) (n > 3) 。ok得到规律这个题就可以直接入手了


int cow(int n)
{
    if (n == 1 || n == 2 || n == 3) return 1;
    return cow(n - 1) + cow(n - 3);
}

但是这肯定不是不是我们的作风，我们要的是实打实的理解。ok我们继续分析，我们从题中可以得知一头牛需要三年成长时间，那么我们假设现在是第n年(n > 3)，那么第n - 3年的牛到第n年的时候是不是都长大了，然后这些都长大的牛会在第n年提供cow(n - 3)的小牛，也就是他们(第n - 3年)自己数量，你看第4年，是不是在第1年的牛会长大，并且提供一头小牛（因为第1年只有一头牛，也就是只有一头牛到第四年的时候会长大，这里并不是说所有的牛在第n - 3年的时候都是小牛，而是想表达不管是不是小牛，他们到第n年的时候都是长大状态），然后再加上自己本身有cow(n - 1)的牛数量，也就是不生小牛自己有多少牛，其实用文字表达式就是当前牛数量 = 生的数量 + 本来有的数量，转化为数学表达式就是cow(n) = cow(n - 1) + cow(n - 3) (n > 3)。ok又解决了一个。

猴子吃桃：

猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，又多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？

这个题我就不分析了，你们自己尝试着做一下。


#include <iostream>
using namespace std;
 
int sumPeach(int );
 
int main()
{
    int sum;
    sum = sumPeach(1);
    cout << sum;
    return 0;
}
 
int sumPeach(int day)
{
    if (day == 10) return 1;
    else return 2 * sumPeach(day + 1) + 2;
}

给个提示 Sn - 1 = Sn / 2 - 1，要是题目不是第十天，而是未知的那应该怎么做呢？自己思考一下吧。有结果可以留言。

接下来就进入正题吧。

3.初识DFS（深度优先遍历）

这里声明一下，有深度优先遍历那肯定就有广度优先遍历，广度我用的比较少，不是很熟悉就不阐述了。

我们先谈谈自己是在什么地方第一次听见这个DFS，我是在上数据结构的时候在树的那一章认识了DFS，树的遍历，前序遍历，中序遍历，后序遍历，前序遍历用的就是DFS，然后在学习图论的时候也用到了DFS。这里就不阐述树的DFS了（因为最近在学习关于二叉树的算法知识，还不是那么懂，就不误人子弟了）。

200. 岛屿数量（力扣链接）

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

题目的意思就是0代表水，1是陆地，然后连起来的1或者单独的1就是岛屿，所以看示例1，里面的1都是连在一起的，所以岛屿数量为1。示例2，左上角四个1连在一起，然后中间一个单独的，右下角又是两个连在一起，所以是3。这个题可以使用DFS，在图论中我们就使用过用DFS来遍历整个图，那么在这里我们也可以用DFS来遍历整个二维数组。

首先我们构造思维，我们起始点就从（0，0）开始，然后是1的话就往他的四个方向寻找

往四个方向找的时候要注意有没有越界，然后四个方向又分开一个一个来，这里就只有两个方向了，因为上面和左边越界了，假设我们先找的是（0，1），那么现在我们要以（0，1）为中心开始往四个方向寻找，这里要注意一个点，（0，0）是已经访问过了的，那么我们需要用一个标识去做标记，表明这个地方已经来过了，要不然就会陷入死循环，只要方向中有是1的，我们就要跳转到他的位置，以他为中心往四个方向寻找，找到0的时候就可以返回，跟越界是一个道理，不用管。这样相当于找到了一个岛屿（由1相连的区域）。这里我就没有一个代码一个代码解释了，我写了注释在上面。


class Solution 
{
public:
    const int dx[4] = {1,-1,0,0};
    const int dy[4] = {0,0,1,-1};
    int numIslands(vector<vector<char>>& grid) 
    {
        int cnt = 0;
        // 开始循环
        for(int i = 0; i < grid.size(); ++i)
            for(int j = 0; j < grid[0].size(); ++j)
                if(grid[i][j] == '1')    // 是1我们才以他为中心寻找
                {
                    ++cnt;
                    DFS(grid, i, j);    // 进入递归，将与（i，j）相连的1全部标记
                }
        return cnt;
    }
    void DFS(vector<vector<char> >& grid, int x, int y)
    {
        // 是1才以他为中心
        if(grid[x][y] == '1')
        {
            grid[x][y] = '0';    // 要置为0证明这个地方已经访问过了
            for(int i = 0; i < 4; ++i)    // 往四个方向寻找
            {
                int xx = x + dx[i], yy = y + dy[i];
                // 必须满足不越界
                if(xx >= 0 && xx < grid.size() && yy >= 0 && yy < grid[0].size())
                    DFS(grid, xx, yy);        //没有越界就递归一下，不用管他是1还是0，
                                              //因为开头会判断
            }
        }
    }
};

695. 岛屿的最大面积（链接力扣）

题目你们就自己点进去看吧，举一反三一下，两个题差不多。


class Solution 
{
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int n;
        for(int i = 0; i < grid.size() ;i++)
            for(int j = 0; j < grid[0].size() ;j++)
                if(grid[i][j] == 1)
                {
                    int cnt = 0;
                    dfs(grid,cnt,i,j);
                    if(cnt >= n)
                        n = cnt;
                }
        return n;
    }
    const int dx[4] = {1, 0, 0, -1};
    const int dy[4] = {0, 1, -1, 0};
    void dfs(vector<vector<int>>& grid, int & cnt,int x,int y)
    {
        if(grid[x][y] == 1)
        {
            cnt++;
            grid[x][y] = 0;
            for(int i = 0;i < 4 ;i++)
            {
                int xx = dx[i] + x, yy = dy[i] + y;
                if(xx >= 0 && xx < grid.size() && yy >= 0 && yy < grid[0].size())
                    dfs(grid,cnt,xx,yy);
            }
        }
    }
};

如果还想要写上述这种类型题，直接在题库搜索岛屿，这样会出现很多这种类型题。

上面两个题其实在图论中的遍历都有体现，接下来我们来讲一些不一样的DFS。

4.记忆化搜索（DFS）

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。（复制来的概念）

以我的了解来说，我觉得记忆化搜索就是DFS的一种，只不过多了一些剪枝（就是优化，可以减少递归次数）内容，然后可以随时保留值。多说无益，直接举例吧。

77. 组合（力扣链接）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

我们先来分析这个题，给了一个1 -- n的范围，然后可以选取k个数组合一起，这一看不就是高中学习的组合呀，组合谁都会，可是要用代码实现出来，好像有点没有思路。这里我选择用DFS + 状态选择。

看示例1，范围是[1，4]，我们可以选取两个数，那我们还是先枚举试试，看有没有什么规律，

假设第一次我们选择1，那么我们还能再选一个，我们第二次选择了2，那没位置可以继续选了，组合就是[1，2]，那我们第二次是不是可以不选择2，跳过2选择下一位，那么组合就是[1，3]，那如果3也跳过呢，那组合就变成了[1，4]，那我们在极端一点，我连1都不要，我直接从2开始选，我们就会发现这不就是在重复第一次选1的步骤吗。也许这就有了一个规律，当我们找到一个点的时候，我们有两种选择，选他和不选他，选不选取决于你。但是我们有一个点要注意，我们选择好一个组合之后，要想重新选择，就要回退，直接代码演示吧


class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) 
    {
        dfs(1, n, k);
        return ans;
    }
    // cur代表当前数字，n代表最大范围，k代表能选多少个
    void dfs(int cur, int n, int k) 
    {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) return;
        // 记录合法的答案
        if (temp.size() == k) 
        {
            ans.emplace_back(temp);     // 将temp存入ans中
            return;
        }
        // 考虑选择当前位置
        temp.emplace_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
};

我们先不看dfs中的第一个if语句，这是个剪枝语句，temp是用来临时存储数字的，也就是上面提到的我先选什么，然后选什么，我们都是存进temp，上面提到了回退，也就是直接踢出temp最后一个进去的元素，让其他数字去进入，我们来一个一个分析，第二个if语句直接判断当前存储的数字够了没有，够了可以直接存到最终的储存工具（ans）里面去了。然后往下走，就是到了我们选择的地方了，我们有两个选择，一个是选他，选了他那我们就把他存进temp.emplace_back(cur)，并且直接进入下一次递归 dfs(cur + 1, n, k)，因为我们选了那肯定要直接跳到下一个数去了，然后在下一个数那里做出我们新的选择。当我们在递归里转了一圈回来了之后，我们又要开始另一个选择，那就是不选他，但是我们前面已经把cur记录进去了，所以我们要退回，也就是 temp.pop_back()，然后再进入下一次递归dfs(cur + 1, n, k)。再讲一下剪枝，在一些题中，剪枝非常重要，这样可以节省大部分时间，就以这个题来说，这个剪枝是什么情况呢，如果我把后面所有的数都选了，但还是凑不齐k个数，那我就没有必要继续下去了，这样是不会有结果的。就像篮球三分大赛一样，有些人一开始手感不好，即使后面的球都进了那也不可能拿冠军了，但是他们不能像我们程序一样直接放弃，人家毕竟是有竞技精神的。

提供另一种写法（感兴趣自己琢磨一下）


class Solution 
{
public:
    vector<int> temp;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) 
    {
        DFS(1, n, k);
        return ans;
    }
    void DFS(int start, int n, int k)
    {
        if(temp.size() == k)
        {
            ans.push_back(temp);
            return;
        }
        for(int i = start; i <= n - (k - temp.size()) + 1; ++i)
        {
            temp.push_back(i);
            DFS(i + 1, n , k);
            temp.pop_back();
        }
    }
};

78. 子集（力扣链接）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

我就直接给出代码了


class Solution 
{
public:
    vector<int> t;
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(0, nums);
        return ans;
    }
    // cur是当前下标和要存储的数量
    void dfs(int cur, vector<int>& nums) 
    {
        // 递归终止条件
        if (cur == nums.size()) 
        {
            ans.push_back(t);
            return;
        }
        // 选择
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);
        t.pop_back();
        // 不选择
        dfs(cur + 1, nums);
    }
};

这个基本思路是和上面是一样的，不一样的地方就是递归终止的条件不一样，这里我们要遍历到最后一个下标的时候就不能再往后面继续进行操作了，那这就是递归的终止条件。

我再给出另一种写法


class Solution 
{
public:
    vector<vector<int> > res;
    vector<int> temp;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        if(nums.size() == 0) return res;
        DFS(nums, 0);
        return res;
    }
    void DFS(vector<int>& nums, int start)
    {
        res.emplace_back(temp);
        for(int i = start; i < nums.size(); ++i)
        {
            temp.emplace_back(nums[i]);
            DFS(nums, i + 1);
            temp.pop_back();
        }
    }
};

784. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

先给代码吧


class Solution 
{
public:
    vector<string> res;
    vector<string> letterCasePermutation(string s) 
    {
        if(s.length() == 0) return res;
        DFS(s,0);
        return res;
    }
    void DFS(string s,int start)
    {
        if(s.length() == start)
        {
            res.emplace_back(s);
            return;
        }
        // 进行大小写转化
        if((s[start] >= 65 && s[start] <= 90) || (s[start] >= 97 && s[start] <= 122))
        {
            // 先变化
            s[start] = s[start] - 'a' >= 0 ? s[start] - 32 : s[start] + 32;
            DFS(s,start + 1);
            s[start] = s[start] - 'a' >= 0 ? s[start] - 32 : s[start] + 32;
            // 经典要回退
        }
        DFS(s,start + 1);
    }
};

这个题我详细分析一下，首先观察题目，我们需要的是把字母大小写变化，如果遍历到数字的话，直接跳过就行，先看第一个if语句，这明显是一个递归终止，当下标到最后的时候先将数据存储，然后就可以结束递归了。往下看第二个if语句是用来判断是不是字母，是字母的话我们先默认改变他的大小写并且进入下一次递归，然后又是退回，进入不改变的递归函数DFS(s, start + 1)。

再来一个难度稍微大一点的题

1601. 最多可达成的换楼请求数目（力扣链接）

这个题我就不在这里赘述了，方法是一样的。直接给出代码，附上我自己写的题解力扣


class Solution 
{
public:
    int res = 0;    // 用来记录最大满足量
    int maximumRequests(int n, vector<vector<int>>& requests) 
    {
        vector<int> dp(n, 0);   // 存储各个楼的进出量，理应最后和最开始都得为0
        DFS(requests.size(), requests, dp, 0, 0);
        return res;
    }
    // i代表当前位置，ans代表满足数
    void DFS(int n, vector<vector<int>>& requests, vector<int>& dp, int i, int ans)
    {
        // 剪枝，如果 最大满足数 大于 后续全部满足 + 当前满足数，那就没有必要继续递归下去了
        // 因为你全部都加上都不可能再大于res了
        if(res > ans + requests.size() - i) return;
        // 下面用来判断当前是否满足了要求净变化为0
        int l;
        for(l = 0; l < dp.size(); ++l)
            if(dp[l] != 0) break;
        // 如果l == dp.size() 代表dp的值都为0，满足净变化量为0
        if(l == dp.size()) res = max(res, ans);
        // 遍历到最后了，也直接结束
        if(i == n) return;
        
        // 下面就是分支选择了，两种选择，1.满足当前i的要求，2.不满足当前i的要求
        // 1.满足
        // 满足要求就要开始记录dp和ans
        --dp[requests[i][0]];
        ++dp[requests[i][1]];
        ++ans;
        DFS(n, requests, dp, i + 1, ans);
        // 结束判断要恢复原来一开始状态
        ++dp[requests[i][0]];
        --dp[requests[i][1]];
        --ans;
        // 2.不满足
        DFS(n, requests, dp, i + 1, ans);
    }
};

5.结尾心得

上面只是举例出了DFS中一小部分题型，目的在于培养一个思维，并不是说你将上面的题都弄懂了，碰到其他的深搜题就一定会，打个比方吧，我们以前学习数学的时候是不是老师都会教我们解题思路，然后我们就依据例题去理解这个思路，但是换一个题还是不会做。不可能通过一小部分点就能把所有的东西都弄懂，所以我们还是得多练，多巩固。这里推荐一个贴子力扣https://leetcode.cn/circle/article/48kq9d/

本人还是一个大二小白，如果上述有什么不到位的地方还望指点出来，争取在以后的贴子里做的更好。

上面有一些图片是从别人那偷过来的，如果侵权了，联系必删。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/596565

DFS（深度优先遍历）举例详解_深度优先遍历 规则 举例

前言：

以下题目均从力扣中获取 力扣