当前位置：首页 > article >正文

递归,搜索与回溯40道算法题

article 2024/9/28 19:02:21

一递归

1汉诺塔问题

2合并两个有序链表

3反转链表

4两两交换链表的节点

5Pow(x,n)

二二叉树的深搜

1计算布尔二叉树的值

2求根节点到叶节点数字之和

3二叉树剪枝

4验证二叉搜索树

5二叉搜索树中第K小的元素

6二叉树的所有路径

三穷举vs暴搜vs深搜vs回溯vs剪枝

1全排列

2子集

四综合联系

1找出所有子集的异或总和再求和

2全排列Ⅱ

3电话号码的字母组合

4括号生成

5组合

6目标和

7组合总和

8字母大小写全排列

9优美的排列

10N皇后

11有趣的数独

12解数独

13单词搜索

14黄金矿工

15不同路径Ⅲ

五floodfill算法

1图像渲染

2岛屿数量

3岛屿的最大面积

4被环绕的区域

5太平洋大西洋水流问题

6扫雷游戏

7衣橱整理

六记忆化搜索

1斐波那契数

解法1：递归 O(2^N)

解法2：记忆化搜索 O(N)

解法3动态规划 O(N) O(N)

2不同路径

3最长递增子序列

4猜数字大小II

5矩阵中的最长递增路径

一递归

1汉诺塔问题

oj链接：汉诺塔问题

先进行画图分析

N=2时，为了最下面的盘子解放，我们直接将（一个）盘子移到B上

而N=3时，为了最下面的盘子解放，(参考N=2)我们需要想办法将2个盘子移到B上，有办法吗？

当然有，借助C间接完成该操作~

然后我们将最大（解放）的盘子移到C上，那下一步呢？

将B上的全部盘子通过A的帮助移到C上，怎么做的问题就转化为：

N=2时将A上的全部盘子通过B的帮助移到C的思路是类似的~(只是柱子对象发生改变了而已)

重复子问题：

设A上盘子数量为N(N>1)

将A上的N-1个盘子通过C的帮助下移到B上（相信递归能帮助我们做到）

剩下的最大的盘子直接移到C上

将B上的N-1个盘子通过A的帮助下移到C上，完成任务~

设计函数头：

要有A,B,C三个vector容器进行数据移动，而且也要有表示当前盘子的数量：

dfs(N，A，B，C) -> n个盘子全部在A上（开始情况）

dfs(N-1，A，C，B) -> 将A上n-1个盘子借助C全部移到B上(递归后,B=C,C=B)

dfs(N-1，B，A，C) -> 将B上n-1个盘子借助A全部移到C上(递归后,A=B,B=A)

递归出口：

当N==1时，函数参数的A上盘子数量只有一个，直接移到C上即可~

注意：以上在dfs调用时A不一定是我们原来说的那个A，有可能变了B,C

只有调用结束后，返回到原函数时，此时函数的A才是我们说的那个A！

class Solution {
public:
    void dfs(int N,vector<int>& A,vector<int>& B,vector<int>& C)
    {
        if(N==1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        //n-1个盘子 A->B
        dfs(N-1,A,C,B);
        //1个盘子 A->C
        C.push_back(A.back());
        A.pop_back();

        //n-1个盘子 B->C
        dfs(N-1,B,A,C);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        int N=A.size();
        dfs(N,A,B,C);
    }
};

2合并两个有序链表

oj链接：合并两个有序链表

思路1：通过while循环：判断两个链表那个节点小就把它插入到新定义的链表中（可以是带头节点的，也可以是不带头节点的），然后将该节点对应的链表进行移动..直到其中有一个链表为空就停止循环

将剩下不为空的链表接到新链表中即可~

// no head
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *ret = nullptr, *cur = nullptr;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                if (ret == nullptr)
                    ret = cur = list1;
                else
                {
                    cur->next = list1;
                    cur = cur->next;
                }

                list1 = list1->next;
            }
            else
            {
                if (ret == nullptr)
                    ret = cur = list2;
                else
                {
                    cur->next = list2;
                    cur = cur->next;
                }
                list2 = list2->next;
            }
        }
        while (list1)
        {
            if (ret == nullptr)
                ret = cur = list1;
            else
            {
                cur->next = list1;
                cur = cur->next;
            }
            list1 = list1->next;
        }
        while (list2)
        {
            if (ret == nullptr)
                ret = cur = list2;
            else
            {
                cur->next = list2;
                cur = cur->next;
            }
            list2 = list2->next;
        }
        return ret;
    }
};

// head
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *ret = new ListNode(-1);
        ListNode *cur = ret;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                cur->next = list1;
                cur = cur->next;
                list1 = list1->next;
            }
            else
            {
                cur->next = list2;
                cur = cur->next;
                list2 = list2->next;
            }
        }
        while (list1)
        {
            cur->next = list1;
            cur = cur->next;
            list1 = list1->next;
        }
        while (list2)
        {
            cur->next = list2;
            cur = cur->next;
            list2 = list2->next;
        }
        ListNode *ans = ret->next;
        delete ret;
        return ans;
    }
};

思路2：递归

重复子问题：

比较两个链表的头节点那个小，那个就是要返回新链表的头节点

接着：头节点小的链表的next与另一个链表合并成一个有序链表

设计函数头：

参数要有两个链表的头节点，而题目正好符合要求，不用在重新写

递归出口：

当其中一个链表为空时，自己返回另一个链表

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

3反转链表

oj链接：反转链表

思路1：定义新链表：循环进行头插法

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *ret = new ListNode(-1);
        ListNode *cur = ret;
        while (head)
        {
            ListNode *next = head->next;
            head->next = cur->next;
            cur->next = head;
            head = next;
        }
        ListNode *ans = ret->next;
        delete ret;
        return ans;
    }
};

思路2：递归

重复子问题：

让当前节点后面的链表先逆置，得到逆置完后链表的头节点

将当前节点连接到逆置完后的链表的尾部

返回逆置完后链表的头节点（一层一层往上呈递上去）

设计函数头：

由于返回值要返回头节点，参数有要进行逆置的链表的头节点，题目所给正好符合~

递归出口：

当节点为空或者节点的下一个节点为空时，返回该节点

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *phead = reverseList(head->next);
        ListNode *cur = phead;
        while (cur->next)
            cur = cur->next;
        cur->next = head;
        head->next = nullptr;
        return phead;
    }
};

4两两交换链表的节点

oj链接：两两交换链表中的节点

思路1：利用while循环进行两两交换并连入新定义的链表

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode *ret = new ListNode(-1);
        ListNode *cur = ret;
        while (head && head->next)
        {
            ListNode *cur1 = head->next;//储存
            ListNode *next = head->next->next;

            head->next->next = head;
            head->next = nullptr;
            cur->next = cur1;

            cur = cur->next->next;
            head = next;
        }
        if (head)//剩下一个节点
            cur->next = head;
        ListNode *ans = ret->next;
        delete ret;
        return ans;
    }
};

思路2：递归

重复子问题：

让当前节点->next->next的链表先逆置，得到逆置完后的链表的头节点

当前节点->next与逆置完后的链表进行连接即可~

返回两两交换节点的第二个节点(提前储存)

设计函数头：

由于返回值要返回头节点，参数有要进行逆置的链表的头节点，题目所给正好符合~

递归出口：

当节点为空或者节点的下一个节点为空时，返回该节点

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode *tmp = swapPairs(head->next->next);

        ListNode *ret = head->next; // head->next提前储存
        head->next->next = head;
        head->next = tmp;

        return ret;
    }
};

5Pow(x,n)

oj链接：Pow(x, n)

思路1：直接x*x*x..的进行n次相乘，但遇到n太大时会栈溢出，不合适~

class Solution {
public:
    double myPow(double x, int n) 
    {
        if(n==0) return 1;

        if(n>0)
        {
            double tmp=myPow(x,n/2);
            return n%2==0?tmp*tmp:tmp*tmp*x;
        }
        else
        {
            int m=-(long long)n;
            double tmp=myPow(x,m/2);
            return m%2==0?1/(tmp*tmp):1/(tmp*tmp*x);
        }
    }
};

思路2：递归

重复子问题：

当n为偶数时，将pow(x,n)进行拆分为：两个pow(x,n/2)进行相乘:而pow(x,n/2)可进行拆分为：两个pow(x,n/2/2)进行相乘...（为了保证递归时不栈溢出,可以先求出拆分数值再相乘）

但n为奇数时，pow(x,n)拆分是：两个pow(x,n/2)进行相乘后再与x相乘(奇数除二取整)

设计函数头：

返回值要返回计算结果，参数有x和n，题目所给符合~

递归出口：

当n==0时，返回1即可

细节问题：

1.n为负数时要单独考虑

2.n==2^31-1转化为正数时有可能溢出

class Solution
{
public:
    double myPow(double x, int n)
    {
        if (n == 0)
            return 1;

        if (n > 0)
        {
            double tmp = myPow(x, n / 2);
            return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
        }
        else
        {
            long long m = -(long long)n; // 数据溢出处理
            double tmp = myPow(x, m / 2);
            return m % 2 == 0 ? 1 / (tmp * tmp) : 1 / (tmp * tmp * x);
        }
    }
};

二二叉树的深搜

1计算布尔二叉树的值

oj链接：计算布尔二叉树的值

重复子问题：

从叶子节点往上进行计算

设计函数头：

题目所给符合

递归出口：

（题目二叉树是固定的）当root->left==null时，根据val进行返回

class Solution
{
public:
    bool evaluateTree(TreeNode *root)
    {
        if (root->left == nullptr)
            return root->val == 0 ? false : true; // 二叉树是完整二叉树

        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);
        return root->val == 2 ? left | right : left & right;
    }
};

2求根节点到叶节点数字之和

oj链接：求根节点到叶节点数字之和

重复子问题：

1.得到这层的数字

2.进行递归，得到左子树最终数字之和

3.进行递归，得到右子树最终数字之和

4.将结果进行返回

设计函数头：

参数root，还要sum表示当前数字值；return 返回结果

递归出口：

如果节点时叶子节点就自己返回当前数字值

class Solution
{
public:
    int sumNumbers(TreeNode *root)
    {
        return dfs(root, 0);
    }
    int dfs(TreeNode *root, int presum)
    {
        int sum = presum * 10 + root->val;
        // 出口
        if (root->left == nullptr && root->right == nullptr)
            return sum;
        // 左右相加
        int ret = 0;
        if (root->left != nullptr)
            ret += dfs(root->left, sum);
        if (root->right != nullptr)
            ret += dfs(root->right, sum);

        return ret;
    }
};

3二叉树剪枝

oj链接：二叉树剪枝

重复子问题：

1.进行递归，得到左子树的节点

2.进行递归，得到右子树的节点

3.根据得到的新的root的情况来进行返回

设计函数头：

参数root，return 新二叉树

递归出口：

如果节点为空返回空

class Solution
{
public:
    TreeNode *pruneTree(TreeNode *root)
    {
        if (root == nullptr)
            return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
            return nullptr;
        return root;
    }
};

4验证二叉搜索树

oj链接：验证二叉搜索树

二叉搜索树的性质：中序遍历是有序的

重复子问题：

1.进行递归，得到左子树是否是二叉搜索树

2.用一个全局变量(最小值)与当前节点值进行比较，并将变量改为节点值

3.进行递归，得到右子树是否是二叉搜索树

设计函数头：

题目符合要求

递归出口：

如果节点为空返回true

class Solution
{
public:
    long long prev = LONG_MIN;
    bool isValidBST(TreeNode *root)
    {
        if (root == nullptr)
            return true;
        bool ret = true;

        ret &= isValidBST(root->left);

        if (ret == false)
            return false; // 剪枝

        if (root->val <= prev)
            ret &= false;
        prev = root->val;

        if (ret == false)
            return false; // 剪枝

        ret &= isValidBST(root->right);
        return ret;
    }
};

5二叉搜索树中第K小的元素

oj链接:二叉搜索树中第 K 小的元素

重复子问题：

由于二叉树是二叉搜索树（中序遍历是从小到大），所以找第K小的数只需进行遍历查找

我们用两个全局变量:count记录要查找的第几个数，tmp记录当前位置的数值(如果count==k就说明找到了，往上返回即可)

设计函数头：

参数root return为空

递归出口：

如果结点为空返回

class Solution
{
public:
    int count = 0, ret = 0;
    int kthSmallest(TreeNode *root, int k)
    {
        if (root == nullptr)
        {
            return 0;
        }
        kthSmallest(root->left, k);
        count++;
        if (count == k)
            ret = root->val;

        kthSmallest(root->right, k);

        return ret;
    }
};

6二叉树的所有路径

oj链接:二叉树的所有路径

重复子问题：

1.要找到二叉树的所有路径，只需进行前序遍历即可;

2.如果考虑都用全局变量:string path记录当前路径，vector<string> ret记录所有路径

问题:path往下递归时每次都要加"val和->":

a.如果递归到空结点时"->"要去掉，添加到ret后往上返回?

b.还是遇到叶子结点添加"val"后停止递归，添加到ret,再将val去掉，最后往上返回？

可见:path作为全局变量很麻烦！

我们考虑path作为局部变量就没有上面的问题了！(每一层的path不会影响另一层的path)

直接:遇到叶子结点加"val"，其它情况加"val ->"

设计函数头：

参数:root,path return 为空

递归出口：

如果结点为空返回

class Solution
{
public:
    vector<string> ret;
    vector<string> binaryTreePaths(TreeNode *root)
    {
        dfs(root, "");
        return ret;
    }
    void dfs(TreeNode *root, string path)
    {
        if (root == nullptr)
            return;

        if (root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            ret.push_back(path);
            return;
        }

        path += to_string(root->val);
        path += "->";
        dfs(root->left, path);
        dfs(root->right, path);
    }
};

三穷举vs暴搜vs深搜vs回溯vs剪枝

关于这类问题，直接画出决策树进行分析问题~

1全排列

oj链接：全排列

画出决策树：

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

bool vis[] 往下一层枚举时剪去当前位置的数值（由false变true）

b设计函数

只需关心每一层在干什么

c递归出口

当nums.size()==path.size()（到达叶子节点），将pathpush到ret中后return

回溯

1.干掉path的最后一个元素

2.修改vis数组（有true变false）

class Solution
{
public:
    bool check[7];
    vector<int> path;
    vector<vector<int>> ret;
    vector<vector<int>> permute(vector<int> &nums)
    {
        dfs(nums);
        return ret;
    }
    void dfs(vector<int> &nums)
    {

        // 出口
        if (nums.size() == path.size())
        {
            ret.push_back(path);

            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            // 剪枝
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯
                check[i] = false;
                path.pop_back();
            }
        }
    }
};

2子集

oj链接：子集

思路1

画出决策树：

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

b设计函数

dfs(nums,i) i表示当前nums的位置

选 path+=nums[i],dfs(nums,i+1)

不选 dfs(nums,i+1)

c递归出口

当i==nums.size()，将pathpush到ret中后return

回溯

如果有选干掉path的最后一个元素

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 i)
    {
        if (i == nums.size())
        {
            ret.push_back(path);
            return;
        }
        // 选
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        path.pop_back();
        // 不选
        dfs(nums, i + 1);
    }
};

思路2

画出决策树：

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

b设计函数

dfs(nums,pos) pos表示下一次枚举的位置

回溯

干掉path的最后一个元素

在这种思路中由于每个节点都是答案都要收集，所以没有递归出口~

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)
    {
        // 没有剪枝与出口
        ret.push_back(path);
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            // 回溯
            path.pop_back();
        }
    }
};

四综合联系

1找出所有子集的异或总和再求和

oj链接：找出所有子集的异或总和再求和

与求子集的思路一样：回溯时注意异或消消乐（同一个数异或两次抵消）即可

class Solution
{
public:
    int path = 0, ret = 0;
    int subsetXORSum(vector<int> &nums)
    {
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int> &nums, int i)
    {
        if (i == nums.size())
        {
            ret += path;
            return;
        }

        path ^= nums[i];
        dfs(nums, i + 1);
        path ^= nums[i];

        dfs(nums, i + 1);
    }
};

2全排列Ⅱ

oj链接：全排列 II

画出决策树：

这里主要是剪枝麻烦~其它与全排列一致

剪枝

1.在同一节点的所有分支中，相同元素只能出现一次 --> 怎么判断？

a.只关心不合法的‘分支’

i!=0 && nums[i] == nums[i-1] && !vis[i-1]

b.只关心合法的‘分支’

i==0 || nums[i] != nums[i-1] || vis[i-1]

而 vis[i-1] 的意思是：nums[i] ==nums[i-1] 但我是合法的~

2.同一个元素只能使用一次 -> bool vis解决

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool vis[8] = {false};
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        // 先排序
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ret;
    }
    void dfs(vector<int> &nums)
    {
        if (path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            // if(!(vis[i]||(i>0&&nums[i]==nums[i-1]&&!vis[i-1]))) 不合法分支
            if (!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) // 合法分支
            {
                vis[i] = true;
                path.push_back(nums[i]);
                dfs(nums);
                path.pop_back();
                vis[i] = false;
            }
        }
    }
};

3电话号码的字母组合

oj链接：电话号码的字母组合

画出决策树：

这里主要解决数字与字符串的映射关系 --> 用字符串数组一一映射解决~

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

vector<string> check 数字与字符串一一映射

b设计函数

dfs(nums,pos) pos表示下一次枚举的位置

回溯

干掉path的最后一个元素

递归出口

当path.size()==digits.size()时：收集叶子结点后返回

class Solution
{
public:
    vector<string> ret;
    string path;
    bool vis[10];
    vector<string> check = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0)
            return ret;
        dfs(digits, 0);
        return ret;
    }
    void dfs(string digits, int pos)
    {
        if (path.size() == digits.size())
        {
            ret.push_back(path);
            return;
        }
        string tmp = check[digits[pos] - '0'];
        for (auto &c : tmp)
        {
            path += c;
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

4括号生成

oj链接：括号生成

做题之前要明白什么是‘有效括号’

1.左括号的数量 = 右括号的数量

2.从头开始的任意子串：左括号数量 >= 右括号数量

画出决策树：

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

int left,right 表示左，右括号数量

b设计函数

dfs(nums)

回溯

干掉path的最后一个元素

递归出口

当右括号数量 == n时收集叶子节点后返回

class Solution
{
public:
    vector<string> ret;
    string path;
    int left = 0, right = 0;
    vector<string> generateParenthesis(int n)
    {
        dfs(n);
        return ret;
    }
    void dfs(int n)
    {
        if (path.size() == n * 2)
        {
            ret.push_back(path);
            return;
        }
        // 选左括号
        if (left < n)
        {
            path += '(';
            left++;
            dfs(n);
            path.pop_back();
            left--;
        }
        // 选右括号
        if (left > right)
        {
            path += ')';
            right++;
            dfs(n);
            path.pop_back();
            right--;
        }
    }
};

5组合

oj链接：组合

画出决策树：

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子节点

vector<int> path 枚举每层的节点

b设计函数

dfs(n,k,pos) --> pos记录枚举的位置（往后枚举）

回溯

干掉path的最后一个元素

递归出口

当 path.size() == k时收集叶子节点后返回

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> combine(int n, int k)
    {
        dfs(n, k, 1);
        return ret;
    }
    void dfs(int n, int k, int pos)
    {
        if (path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(n, k, i + 1);
            path.pop_back();
        }
    }
};

6目标和

oj链接：目标和

画出决策树：

设计代码：

a全局变量

int ret 收集符合的情况和

int aim 全局的目标和

b设计函数

dfs(nums,pos,sum) --> pos 记录当前位置 sum当前和

回溯

无

递归出口

当 nums.size() == pos时看参数是否等于aim来判断ret是否++ 返回

class Solution
{
public:
    int ret = 0, aim = 0;
    int findTargetSumWays(vector<int> &nums, int target)
    {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    void dfs(vector<int> &nums, int pos, int path)
    {
        if (pos == nums.size())
        {
            if (path == aim)
                ret++;
            return;
        }
        // 加法
        dfs(nums, pos + 1, path + nums[pos]);
        // 减法
        dfs(nums, pos + 1, path - nums[pos]);
    }
};

7组合总和

oj链接：组合总和

思路1

画出决策树

根据当前位置往后来枚举组合总和

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子结点

vector<int> path 当前每层节点

int aim 目标和

b设计函数

dfs(candidates,pos,sum) --> pos 从当前位置开始 sum 当前位置和

回溯

干掉最后一个元素

递归出口

当sum >=aim时看sum是否等于aim来决定 ret.push_back(path) 最后往上返回

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int aim;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int> &candidates, int pos, int sum)
    {
        if (sum >= aim)
        {
            if (sum == aim)
            {
                ret.push_back(path);
            }
            return;
        }

        for (int i = pos; i < candidates.size(); i++)
        {
            path.push_back(candidates[i]);
            dfs(candidates, i, sum + candidates[i]);
            path.pop_back();
        }
    }
};

思路2

画出决策树

根据当前位置要枚举多少个来进行组合总和

设计代码：

a全局变量

vector<vector<int>> ret 收集叶子结点

vector<int> path 当前每层节点

int aim 目标和

b设计函数

dfs(candidates,pos,sum) --> pos 从当前位置开始 sum 当前位置和

回溯

当前层所有情况枚举完才恢复现场

递归出口

当 sum == aim ret.push_back(path) 往上返回

当 sum >aim || pos == candidates.size() 往上返回

class Solution
{
public:
    int aim = 0;
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int> &candidates, int pos, int sum)
    {
        if (sum == aim)
        {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == candidates.size())
            return;
        // 枚举个数
        for (int i = 0; sum + i * candidates[pos] <= aim; i++)
        {
            if (i)
                path.push_back(candidates[pos]);
            dfs(candidates, pos + 1, sum + i * candidates[pos]);
        }

        // 所有情况枚举完才回溯
        for (int i = 1; sum + i * candidates[pos] <= aim; i++)
        {
            path.pop_back();
        }
    }
};

8字母大小写全排列

oj链接：字母大小写全排列

画出决策树

设计代码：

a全局变量

vector<string> ret 收集叶子结点

string path 当前每层节点

b设计函数

dfs(s,pos) --> pos 当前位置

回溯

干掉最后一个元素

递归出口

当path.size()== pos 收集结果向上返回

class Solution
{
public:
    vector<string> ret;
    string path;
    int n;
    vector<string> letterCasePermutation(string s)
    {
        n = s.size();
        dfs(s, 0);
        return ret;
    }
    void dfs(string s, int pos)
    {
        if (pos == n)
        {
            ret.push_back(path);
            return;
        }

        // 不改
        path += s[pos];
        dfs(s, pos + 1);
        path.pop_back();

        // 改
        if (s[pos] < '1' || s[pos] > '9')
        {
            char tmp = change(s[pos]);
            path.push_back(tmp);
            dfs(s, pos + 1);
            path.pop_back();
        }
    }
    char change(char tmp)
    {
        if (tmp >= 'a' && tmp <= 'z')
            tmp -= 32;
        else
            tmp += 32;
        return tmp;
    }
};

9优美的排列

oj链接：优美的排列

画出决策树

设计代码：

a全局变量

int ret 收集叶子结点

vector<int> path 当前每层节点

bool vis[15] 去重

b设计函数

dfs(n,pos) --> pos 当前位置

回溯

干掉最后一个元素

vis[i]=false

递归出口

当path.size()== n 收集结果向上返回

class Solution
{
public:
    int ret;
    vector<int> path;
    bool vis[15]={false};
    int countArrangement(int n)
    {
        dfs(n, 1);
        return ret;
    }
    void dfs(int n, int pos)
    {
        if (path.size() == n)
        {
            ret++;
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && (i % pos == 0 || pos % i == 0))
            {
                vis[i] = true;
                path.push_back(i);
                dfs(n, pos + 1);
                path.pop_back();
                vis[i] = false;
            }
        }
    }
};

10N皇后

oj链接：N 皇后

画出决策树（不重要）

主要：剪枝 + 代码

设计代码：

a全局变量

vector<vector<string>> ret 收集叶子结点

vector<string> path 当前每层节点

bool col[10] bool diag1[20] bool diag2[20] 剪枝

b设计函数

dfs(row) --> row 当前所在行数

回溯

将‘Q’的位置修改为‘.’

col diag1 diag2 修改为 false

递归出口

当row== n 收集结果向上返回

class Solution
{
public:
    vector<vector<string>> ret;
    vector<string> path;
    bool col[10] = {false}, diag1[20] = {false}, diag2[20] = {false};
    vector<vector<string>> solveNQueens(int n)
    {
        path.resize(n);
        for (int i = 0; i < n; i++)
        {
            path[i].resize(n, '.');
        }
        dfs(n, 0);
        return ret;
    }
    void dfs(int n, int row)
    {
        if (row == n)
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) // 枚举每行的位置
        {
            if (!col[i] && !diag1[i - row + n] && !diag2[i + row + n])
            {
                path[row][i] = 'Q';
                col[i] = diag1[i - row + n] = diag2[i + row + n] = true;
                dfs(n, row + 1);
                path[row][i] = '.';
                col[i] = diag1[i - row + n] = diag2[i + row + n] = false;
            }
        }
    }
};

11有趣的数独

oj链接：有效的数独

此题严格来说不算是dfs类问题但有点像

全局变量

bool row[9][10] col[9][10] diag[3][3][10] 来进行判断是否出现重复数字即可（空间换时间）

class Solution
{
public:
    bool row[9][10] = {false};
    bool col[9][10] = {false};
    bool grid[3][3][10] = {false};
    bool isValidSudoku(vector<vector<char>> &board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[i].size(); j++)
            {
                if (board[i][j] != '.')
                {
                    int tmp = board[i][j] - '0';
                    if (!row[i][tmp] && !col[j][tmp] && !grid[i / 3][j / 3][tmp])
                    {
                        row[i][tmp] = col[j][tmp] = grid[i / 3][j / 3][tmp] = true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

12解数独

oj链接：解数独

借助上题的方法：用三个全局变量判断数独是否重复了

全局变量

bool row[9][10] col[9][10] diag[3][3][10]

b设计函数

bool dfs(board) --> 每个'.'进行1-9数字尝试,如果出现填不了的情况要告诉上层false了

class Solution
{
public:
    bool row[9][10] = {false}, col[9][10] = {false};
    bool diag[3][3][10] = {false};
    void solveSudoku(vector<vector<char>> &board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] != '.')
                {
                    int tmp = board[i][j] - '0';
                    row[i][tmp] = col[j][tmp] = diag[i / 3][j / 3][tmp] = true;
                }
            }
        }
        dfs(board);
    }

    bool dfs(vector<vector<char>> &board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k <= 9; k++)
                    {
                        if (!row[i][k] && !col[j][k] && !diag[i / 3][j / 3][k])
                        {
                            board[i][j] = k + '0';
                            row[i][k] = col[j][k] = diag[i / 3][j / 3][k] = true;
                            if (dfs(board))
                                return true;
                            // 恢复现场
                            board[i][j] = '.';
                            row[i][k] = col[j][k] = diag[i / 3][j / 3][k] = false;
                        }
                    }
                    return false; // 1-9到尝试完了
                }
            }
        }
        return true; // 填完了
    }
};

13单词搜索

oj链接：单词搜索

画出决策树

主要：写代码

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0} 表示出上下左右四个位置

bool vis[][] 走过的位置进行标记

b设计函数

bool dfs(board,i,j,word,pos) --> pos 当前word的位置

回溯

vis[i][j] = false 返回到上一层进行恢复现场

递归出口

当word.size() == pos 时说明找到了word字符串了，返回true

class Solution
{
public:
    //利用向量方式定义出上下左右四个位置
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[7][7] = {false};
    int m, n;
    bool exist(vector<vector<char>> &board, string word)
    {
        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;
                    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 = dx[k] + i, y = dy[k] + j;
            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;
    }
};

14黄金矿工

oj链接：黄金矿工

与上题类似：进行dfs四个方向的深搜：找出最大的一次收益即可

class Solution
{
public:
    bool vis[16][16] = {false};
    int ret = 0, m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    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] != 0)
                {
                    vis[i][j] = true;

                    dfs(grid, i, j, 0);
                    vis[i][j] = false;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>> &grid, int i, int j, int sum)
    {
        ret = max(ret, sum += grid[i][j]);
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y])
            {
                vis[x][y] = true;
                dfs(grid, x, y, sum);
                vis[x][y] = false;
            }
        }
    }
};

15不同路径Ⅲ

oj链接：不同路径 III

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0}

int count 统计要走的步数

int step 当前位置已经走的步数

int ret 统计方法数

bool vis[][] 去除当前走过的位置

b设计函数

bool dfs(grid,i,j) ->从当前位置(i,j)进行四个方向的搜索

回溯

step-- vis[][]=false

递归出口

当grid[i][j]==2，说明找到了一种方法进行ret++,return返回上一层

class Solution
{
public:
    int count = 0, step = 0, ret = 0;
    bool vis[20][20];
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
    int uniquePathsIII(vector<vector<int>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        int a = 0, b = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)
                    count++;
                if (grid[i][j] == 1)
                    a = i, b = j;
            }
        }
        // 完整路径要加上起始与终止
        count += 2;
        step++;
        vis[a][b] = true;

        dfs(a, b, grid);

        return ret;
    }
    void dfs(int a, int b, vector<vector<int>> &grid)
    {
        if (grid[a][b] == 2)
        {
            if (count == step)
                ret++;
            return;
        }
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + a, y = dy[k] + b;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1)
            {
                step++;
                vis[x][y] = true;

                dfs(x, y, grid);

                step--;
                vis[x][y] = false;
            }
        }
    }
};

五floodfill算法

暴搜的一种有名字的算法~

1图像渲染

oj链接：图像渲染

画出决策树

主要：写代码

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0} 表示出上下左右四个位置

int prev 记录起始位置的color

b设计函数

bool dfs(board,sr,sc,color)

回溯

无

递归出口

无

class Solution
{
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int m, n, prev;
    vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int color)
    {
        if (image[sr][sc] == color)
            return image; // 防止栈溢出

        m = image.size(), n = image[0].size(), prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }
    void dfs(vector<vector<int>> &image, int i, int j, int color)
    {
        image[i][j] = color;
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
            {
                dfs(image, x, y, color);
            }
        }
    }
};

//这种不用判断
class Solution {
public:
    bool vis[50][50]={false};
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m,n,tmp;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {    
        m=image.size(),n=image[0].size(),tmp=image[sr][sc];
        dfs(image,sr,sc,color);
        return image;
    }
    void dfs(vector<vector<int>>& image,int i,int j,int color)
    {
        cout<<i<<' '<<j<<endl;
        image[i][j]=color;
        vis[i][j]=true;

        for(int k=0;k<4;k++)
        {
            int x=dx[k]+i,y=dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&image[x][y]==tmp)
            {
                dfs(image,x,y,color);
            }
        }      
    }
};

2岛屿数量

oj链接：岛屿数量

画出决策树

主要：写代码

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0} 表示出上下左右四个位置

int ret 记录岛屿数量

b设计函数

bool dfs(board,i,j)

回溯

无

递归出口

无

class Solution
{
public:
    bool vis[300][300] = {false};
    int m, n, ret = 0;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int numIslands(vector<vector<char>> &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] == 1 + '0' && !vis[i][j])
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>> &grid, int i, int j)
    {
        vis[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1 + '0')
            {
                dfs(grid, x, y);
            }
        }
    }
};

3岛屿的最大面积

oj链接：岛屿的最大面积

与上题类似~

class Solution
{
public:
    bool vis[50][50] = {false};
    int m, n, count, ret = 0;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int maxAreaOfIsland(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] == 1 && !vis[i][j])
                {
                    count = 0;
                    dfs(grid, i, j);
                    ret = max(ret, count);
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>> &grid, int i, int j)
    {
        count++;
        vis[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
        }
    }
};

4被环绕的区域

oj链接：被围绕的区域

主要：写代码

题目要把被‘X’包围的‘O’修改为‘X’，直接去求很可能，所以我们正难则反:找不被包围的‘O’

从边界进行找‘O’：从该坐标出进行dfs：把找到的‘O’都进行标记(标记的‘O’就不是题目所求)

再对grid进行遍历：此时没被标记的‘O’就是要被修改成‘X’

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0}

bool vis[][] 进行标记‘O’

b设计函数

bool dfs(grid,i,j) i,j表示‘O’的完整

回溯

无

递归出口

无

class Solution
{
public:
    bool vis[200][200] = {false};
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int n, m;
    void solve(vector<vector<char>> &board)
    {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)
        {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][m - 1] == 'O')
                dfs(board, i, m - 1);
        }
        for (int j = 0; j < m; j++)
        {
            if (board[0][j] == 'O')
                dfs(board, 0, j);
            if (board[n - 1][j] == 'O')
                dfs(board, n - 1, j);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!vis[i][j] && board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    void dfs(vector<vector<char>> &board, int i, int j)
    {
        vis[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }
};

5太平洋大西洋水流问题

oj链接：太平洋大西洋水流问题

主要：理解题目

题目要求的是：找出既能流向太平洋，又能流向大西洋的坐标

解法一：直接进行每个点的遍历进行判断（超时）

解法二：正难则反：把能流向太平洋的位置标记；能流向大西洋的位置进行标记

两者都标记的地方就是答案！！

设计代码：

a全局变量

int dx[4] = {0,0,1,-1} dy[4]={1,-1,0,0}

b设计函数

bool dfs(heights,i,j,vis) i j 表示坐标 vis表示被被洋流流到的位置

回溯

无

递归出口

无

class Solution
{
public:
    int n, m;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    void dfs(vector<vector<int>> &heights, int a, int b, vector<vector<bool>> &vis)
    {
        vis[a][b] = true;
        for (int i = 0; i < 4; i++)
        {
            int x = dx[i] + a, y = dy[i] + b;
            if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && heights[x][y] >= heights[a][b])
            {
                dfs(heights, x, y, vis);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights)
    {
        n = heights.size(), m = heights[0].size();
        vector<vector<bool>> pac(n, vector<bool>(m));
        vector<vector<bool>> atl(n, vector<bool>(m));
        // 处理pac
        for (int i = 0; i < m; i++)
            dfs(heights, 0, i, pac);
        for (int j = 0; j < n; j++)
            dfs(heights, j, 0, pac);
        // 处理atl
        for (int i = 0; i < m; i++)
            dfs(heights, n - 1, i, atl);
        for (int j = 0; j < n; j++)
            dfs(heights, j, m - 1, atl);

        vector<vector<int>> ret;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (pac[i][j] && atl[i][j])
                    ret.push_back({i, j});
            }
        }
        return ret;
    }
};

6扫雷游戏

oj链接：扫雷游戏

主要：理解题目+写代码

设计代码：

a全局变量

int dx[4] = {0,0,1,-1,1,1,-1,-1} dy[4]={1,-1,0,0,-1,1,-1,1} 进行8个位置的递归

b设计函数

bool dfs(board,i,j) i j 表示递归的坐标

回溯

无

递归出口

该位置的周围雷时，修改位置后return无需再递归

class Solution {
public:
    int m,n;
    int dx[8]={0,0,1,-1,1,1,-1,-1};
    int dy[8]={1,-1,0,0,-1,1,-1,1};
    //bool vis[51][51]={0};
    void dfs(vector<vector<char>>& board,int a,int b)
    {
        //先标记地雷的个数
        int count=0;
        for(int i=0;i<8;i++)
        {
            int x=dx[i]+a,y=dy[i]+b;
            if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='M') count++;
        }

        if(count!=0)
        {
            board[a][b]=count+'0';
        }

        else
        {
            board[a][b]='B';
            for(int i=0;i<8;i++)
            {
                int x=dx[i]+a,y=dy[i]+b;
                if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='E') dfs(board,x,y);
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m=board.size(),n=board[0].size();
        int x=click[0],y=click[1];
        if(board[x][y]=='M')
        {
            board[x][y]='X';
            return board;
        }
        dfs(board,x,y);
        return board;
    }
};

7衣橱整理

oj链接：衣橱整理

从[0][0]位置开始进行一次dfs统计出格子即可~

class Solution
{
public:
    int dx[2] = {1, 0};
    int dy[2] = {0, 1};
    bool vis[100][100] = {false};
    int ret = 0;
    int wardrobeFinishing(int m, int n, int cnt)
    {
        dfs(m, n, 0, 0, cnt);
        return ret;
    }
    void dfs(int m, int n, int i, int j, int cnt)
    {
        ret++;
        vis[i][j] = true;
        for (int k = 0; k < 2; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y, cnt))
                dfs(m, n, x, y, cnt);
        }
    }
    bool check(int x, int y, int cnt)
    {
        int sum = 0;
        while (x)
        {
            sum += x % 10;
            x /= 10;
        }
        while (y)
        {
            sum += y % 10;
            y /= 10;
        }
        return sum <= cnt;
    }
};

六记忆化搜索

1斐波那契数

oj链接：斐波那契数

解法1：递归 O(2^N)

主要：找规律：第n个数 = 第n-1个数 + 第n-2个数

设计代码：

a全局变量

无

b设计函数

int dfs(n)

回溯

无

递归出口

但n==0或者n==1时返回n

class Solution
{
public:
    int fib(int n)
    {
        return dfs(n);
    }
    int dfs(int n)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }
        return dfs(n - 1) + dfs(n - 2);
    }
};

解法2：记忆化搜索 O(N)

在这道题中我们会发现：在递归时有出现重复，我们可以把结果存到备忘录中，下次用时玩备忘录看看，有就直接返回结果，不用在往下进行递归啦！

如何实现记忆化搜索？(四部曲)

1添加一个备忘录（<可变参数，返回值>）

2备忘录初始化，让里面的值不干扰后续使用

3递归每次返回时，将结果放到备忘录里面

4在每次递归进入之前，往备忘录里瞅一瞅

class Solution
{
public:
    int memo[31] = {0}; // 1添加备忘录
    int fib(int n)
    {
        memset(memo, -1, sizeof(memo)); // 2初始化
        return dfs(n);
    }
    int dfs(int n)
    {
        if (memo[n] != -1)
            return memo[n]; // 4往备忘录瞅一瞅
        if (n == 0 || n == 1)
        {
            memo[n] = n;
            return memo[n];
        }
        memo[n] = dfs(n - 1) + dfs(n - 2); // 3递归结果储存
        return memo[n];
    }
};

解法3动态规划 O(N) O(N)

1状态表示 --> dfs函数的含义

dp[i]表示：第i个斐波那契数

2状态转移方程 --> dfs函数的函数体

dp[i] = dp[i-1] + dp[i-2]

3初始化 --> dfs函数的出口

dp[0]=0,dp[1]=1

4确定填表顺序 --> 填写备忘录的顺序

从左向右

5返回值 --> 主函数是如何调用dfs的

dp[n]

class Solution
{
public:
    int dp[31] = {0};
    int fib(int n)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

问题：

1所有的递归（暴搜，深搜）都能改成记忆化搜索吗？

不是的，只有在递归过程中，出现大量相同的问题时，才能用记忆化搜索优化

2带备忘录的递归 vs 带备忘录的动态规划 vs 记忆化搜索

都是一回事

3自顶向下 vs 自底向上

思考的方向不同：递归是自顶向下，动态规划时自底向上

4我们在做题中能这么做：暴搜 -> 记忆化搜索 -> 动态规划？

80%的题能够往这方向上去思考解决，但不是绝对：但这能为我们的状态表示提供方向

2不同路径

oj链接：不同路径

设计代码：

a全局变量

int memo[][]

b设计函数

int dfs(i,j)

回溯

无

递归出口

当i==1 && j==1时返回1(此时递归到开始处,只有一种路径)

当i==0 || j==0时返回1(此时坐标不合法)

class Solution
{
public:
    int memo[101][101];
    int uniquePaths(int m, int n)
    {
        return dfs(m, n);
    }
    int dfs(int i, int j)
    {
        if (memo[i][j] != 0)
            return memo[i][j];
        if (i == 0 || j == 0)
            return 0;
        if (i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return memo[i][j];
        }
        memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
        return memo[i][j];
    }
};

3最长递增子序列

oj链接：最长递增子序列

设计代码：

a全局变量

int memo[][]

b设计函数

int dfs(pos,nums,memo) -->从pos位置开始往下进行遍历

回溯

无

递归出口

无

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> memo(n);
        int ret = 1;
        for (int i = 0; i < n; i++)
        {
            ret = max(ret, dfs(i, nums, memo));
        }
        return ret;
    }

    int dfs(int pos, vector<int> &nums, vector<int> &memo)
    {
        if (memo[pos] != 0)
            return memo[pos];
        int ret = 1;
        for (int i = pos + 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[pos])
            {
                ret = max(ret, dfs(i, nums, memo) + 1);
            }
        }
        memo[pos] = ret;
        return ret;
    }
};

4猜数字大小II

oj链接：猜数字大小 II

主要理解

找所有策略中的最小现金数（每个策略找出猜到数字时最大的现金数）

设计代码：

a全局变量

int memo[][]

b设计函数

int dfs(a,b) -->在[a,b]区间内进行猜数字

回溯

无

递归出口

a>=b是，返回0

class Solution
{
public:
    int memo[201][201];
    int dfs(int a, int b)
    {
        if (a >= b)
            return 0; // 猜到了
        if (memo[a][b] != 0)
            return memo[a][b];
        int ret = INT_MAX;
        for (int i = a; i <= b; i++)
        {
            ret = min(ret, max(dfs(a, i - 1), dfs(i + 1, b)) + i);
        }
        memo[a][b] = ret;
        return memo[a][b];
    }
    int getMoneyAmount(int n)
    {
        return dfs(1, n);
    }
};

5矩阵中的最长递增路径

oj链接：矩阵中的最长递增路径

设计代码：

a全局变量

int memo[][]

b设计函数

int dfs(i,j,matrix) --> 从该点出发找到最长递增路径

回溯

无

递归出口

无

class Solution
{
public:
    int n, m, ret;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int memo[201][201] = {0};

    int dfs(int a, int b, vector<vector<int>> &matrix)
    {
        if (memo[a][b] != 0)
            return memo[a][b];
        int ret = 1;
        for (int i = 0; i < 4; i++)
        {
            int x = dx[i] + a, y = dy[i] + b;
            if (x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[a][b])
            {
                ret = max(ret, dfs(x, y, matrix) + 1); // 所有路径下的最长路径
            }
        }
        memo[a][b] = ret;
        return memo[a][b];
    }

    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        n = matrix.size(), m = matrix[0].size(), ret = 1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                ret = max(ret, dfs(i, j, matrix)); // 每个数进行遍历，找出最长路径
            }
        }
        return ret;
    }
};