[Lc_1 递归] 递归，搜索与回溯总结 | 详解汉诺塔问题

[Lc_1 递归] 递归，搜索与回溯总结 | 详解汉诺塔问题

引用

CSDN

1.

https://blog.csdn.net/2301_80171004/article/details/146394374

目录
1.递归
2.搜索
3.回溯与剪枝
记忆化搜索 vs dp

1. 思路是什么？
2. 本质理解
3. 问题思考 && 总结
4. 汉诺塔问题
   题解

• 搜索是递归中的一个分支
• 回溯是搜索中的一个分支
• 因此我们学习顺序是递归、搜索、回溯。

1.递归

什么是递归？

• 在C语言，和数据结构（二叉树、快速排序、归并排序）我们或多或少已经接触过递归；
• 递归大白话来说就是：函数自己调用的情况

为什么会用到递归？
以二叉树、快排、归并为例

后序:左右根

• 我们一定是从根节点开始,先找左子树,在找右子树,然后在根节点,
• 当我们走到下面左子树的时候,也依旧是这样的做法
• 等到把左子数遍历完了,然后走到右子树依旧是左右根
• 当右子树走完,才最终回到根节点

快排

• 每次都排一个基准元素 的正确位置，将数组分成两部分
• 然后再对分开的部分在找基准元素然后在继续分…
  

归并

• 选择中间节点将数组分成两部分，分别对于两部分排序
• 然后再合并，然后分解到下面也是一样的操作，

上面都是解决主问题的时候，出现了相同的子问题。

• 主问题 -----> 相同的子问题
• 子问题 -----> 相同的子问题

总结：

• 当出现一个问题，你发现解决这个问题的过程中，会出现相同的子问题
• 并且这些子问题都可以用同一个函数来解决，此时用递归！

如何理解递归？

• 第一层：递归展开图
• 第二层：二叉树中的题目
• 第三层：宏观看待递归的过程

不要在意递归的细节展开图

• 把递归的函数当成一个黑盒(我给黑盒一些数据，黑盒最终能够返回我想要的结果，具体里面是如何操作我并不关心)
• 相信这个黑盒一定能完成这个任务

dfs函数看成一个黑盒，我给你一个根节点，你把这个根节点后序遍历一下。

• 我们要有一个心理暗示，相信这个dfs一定能够完成。
• 接下来就是如何完成，后序先要遍历左子树
• 所以给dfs传入左子树根节点，右子树根节点，关于dfs如何完成并不关心。
• 然后左右子数都完成了，就该根节点了。

void dfs(TreeNode* root)
{
    //细节 出口
    if(root==null) return;
    dfs(root->left);
    dfs(root->right);
    printf(root->val);
}  

如果把递归当成一个黑盒，不用关心那些递归展开图

• 直接看递归函数是如何进行的看某一层是如何操作的，具体是如何展开并不关心，我相信你一定能够完成这个任务。
• 因为我们有之前第一层第二层的铺垫，编译器是会自动帮我们展开完成左子树右子树的遍历。
• 然后再关注细节 出口 问题，这个递归代码就出来了。

快排

void merge(int nums,int left,int right)
{
    //细节 出口
    if(left>=right) return;
    int mind=(left+right)/2;
    merge(nums,left,mid);
    merge(nums,mid+1,right);
    //左边排排 右边排排
    //排好后 递归返回合并
}  

快排 merge看成一个黑盒，我给你一个数组和左端点和右端点，你把这个区间排下序，并且我相信这个黑盒一定能够完成任务。

• 具体如何排序，就是选一个中间节点把数组平方成两部分，左边排好序，右边排好序，如何排序merge就是排序的具体你里面是如何操作的我不管，而且一定能够完成任务，因为以前我画过递归展开图。
• 排好序之后再合并有序数组。
• 注意处理细节不能出现死递归。

如何写好一个递归？

• 1.先找到相同的子问题(确定每次要传什么)！！！ ---->函数头设计
• 2.只关心某一个子问题是如何解决的 ----->函数体的书写
• 3.注意一下递归函数的出口即可

2.搜索

搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜
这些都是在搜索经常会碰见的名词

• 深度优先遍历 vs 深度优先搜索 dfs
• 宽度优先遍历 vs 宽度优先搜索 bfs

深度优先遍历一条路走到黑直到不能走在返回
宽度优先遍历一层一层走

那什么是深度优先搜索和宽度优先搜索呢？
想一个问题，我们遍历的目的是不是为了找到节点里的值啊。

• 所以深度优先遍历和深度优先搜索，宽度优先遍历和宽度优先搜索 其实就是一个东西。
• 遍历是形式，目的是搜索。 其实就是同一个东西！
• 搜索就是在这个树或者图，把所有节点都遍历一遍。

关系图

• 搜索的本质就是：暴力枚举一遍所有的情况。
• 所以搜索也可以叫做暴搜。
• 搜索(暴搜)，把所有情况都暴力枚举一遍。
• 它分为两种情况：1. dfs ，2. bfs

扩展搜索问题
搜索要么是树状结构，要么是图状结构。
其实全排列就是树状结构
此时我们仅需从开始的位置开始把这棵决策树遍历一遍，也就是来一次深度优先遍历就可以把所有结构都可以找到。

• 所以不要把深度优先遍历和宽度优先遍历局限于是必须是二叉树的题目和图的题目
• 如果一个题目能用一个决策树的形式画出来，我们就可以用搜索的形式把所有结果全都暴力枚举处理。

3.回溯与剪枝

回溯本质就是深度优先搜索

• 就比如迷宫问题，解决迷宫问题有两种方式，一个是深度优先遍历，一个是宽度优先遍历。
• 下面我们采用深度优先遍历的方式
• 只要有拐角要么走左边，要么走右边，把所有情况都尝试一遍，一定能找到终点。

如果发现一条路走不通就返回，其中红色这条线就是回溯。

回溯:
就是在找最终结果时尝试某种情况的时候发现某种情况行不通，此时返回上一级然后从上一级继续开始尝试。

• 这不是就是深搜的分支吗返回上一层的操作。
• 回退上一级就是回溯，所以不要把回溯和深搜分开。

当再次回溯到同一点的时候，但是上面的已经走过了不用再走了，这种情况就是剪枝。

剪枝:
就是这条分叉路口有两种选择，但是我们已经明确知道其中一个选择不是我们最终想要的结果，我们就可以把这个分支剪掉。

所以不要把回溯和剪枝想的有多神奇
回溯就是深搜的一个小分支而已

记忆化搜索 vs dp

• 以斐波那契数列举例：

1. 思路是什么？
   记忆化搜索：采用带备忘录的递归方式。

• 其核心是将已经计算过的结果保存起来，避免重复计算。

动态规划一般思路：

• 确定状态表示 -> 明确
  dp[i]
  的含义。
• 推导状态转移方程。
• 初始化：确定基础情况的值。
• 确定填表顺序：即如何根据已知信息更新未知信息。
• 确定返回值：明确最终需要输出的结果。

2. 本质理解

• 大部分情况下，记忆化搜索的代码是可以转换为动态规划代码的。

• 斐波那契数列举例：

• 状态表示：
  dp[i]
  代表第i个斐波那契数。

• 状态转移方程：
  dp[i] = dp[i - 1] + dp[i - 2]
  。

• 初始化：
  dp[0] = 0, dp[1] = 1
  。

• 填表顺序和递归出口对应于DFS()的实现细节。

• 动态规划和记忆化搜索的本质区别在于解决问题的方式：

• 记忆化搜索使用递归来解决问题，而常规的动态规划则采用递推（循环）的方式来填充表格。

• 两者都是对暴力解法（暴搜）的优化，通过存储已经计算过的值来减少重复计算。

3. 问题思考 && 总结

• 并非所有的递归（暴搜、深搜）都能用记忆化搜索的方式进行优化。只有当递归过程中出现大量完全相同的问题时，才能应用记忆化搜索。
• 带备忘录的递归 VS 带备忘录的动态规划 VS 记忆化搜索本质上是一样的，只是在解决问题时采用了不同的思考方式：自顶向下（递归）VS 自底向上（动态规划）。
• 暴搜 -> 记忆化搜索 -> 动态规划这条优化路径大多数情况下有效，但并非绝对。
• 有时直接思考动态规划比从暴搜出发更为直接，这取决于个人以及具体问题的特点。（即 抽象时的 想法）
• 总结来说，这条思考线路为我们确定状态表示提供了一个方向，帮助我们更有效地解决复杂问题。

1. 汉诺塔问题

链接：面试题 08.06. 汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。

示例 1：

输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]  

示例 2：

输入：A = [1, 0], B = [], C = []
 输出：C = [1, 0]  

提示：

1. A 中盘子的数目不大于 14 个。

题解

有三根柱子和一些盘子，将第一根柱子上面所有盘子借助其他柱子移动到最后一根盘子上。
不要看到汉诺塔就马上使用递归，一定知道为什么可以用递归，这比如何用递归解决这个问题更加重要。

1.如何解决汉诺塔问题
我们可以采取 由易到难的模拟 +观察推理

当只有一个盘子的时候，可以直接移动到最后一个柱子上

当有两个盘子的时候

• 1. 将A柱最下面盘子上面的盘子先放到B柱
     
• 2. 将A柱最下面的一个放到C柱
• 3. 然后将B柱上面的盘子在放到C柱

当有三个盘子的时候

• 1. 将A柱最下面盘子上面的盘子先放到B柱
• 2. 将A柱最下面的一个放到C柱
• 3. 然后将B柱上面的盘子在放到C柱

当有四个盘子的时候

• 1. 将A柱最下面盘子上面的盘子先放到B柱
     
• 2. 将A柱最下面的一个放到C柱
• 3. 然后将B柱上面的盘子在放到C柱

2.为什么可以用递归？
当我们发现解决大问题的时候，出现相同类型的子问题。
并且解决方法都是一样的。此时就可以用递归了。

• 大问题 —> 相同类型的子问题
• 子问题 —> 相同类型的子问题

3.如何编写递归？
1.重复的子问题 ----> 函数头

• 我们发现都是一根柱子上的盘子借助另一个柱子将盘子转移到其他柱子上面的，因此我们可以总结出来。
• 将 x 柱子上的一堆盘子，借助 y 柱子，转移到 z 柱子上面 ---->void dfs(x，y，z，int n)

2.只关心某一个子问题在做什么 ----> 函数体

• dfs(x，z，y，n-1)将x柱上n-1个盘子借助z柱，转移到y柱子 第
• x.back() -> z将x柱最后一个盘子，转移到z柱
• dfs(y，x，z，n-1)将y柱上n-1个盘子借助x柱，转移到z柱

我们要以宏观角度理解递归函数，只要给它数据它一定能够帮我们完成任务。
不用管具体的递归过程。

3.递归的出口

• n==1的时候，不用借助其他柱子，直接放就可以了。

• x.back() --> z

根据上面我们就可以写代码了

class Solution {
public:
    void hanota
    (vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        if(A.empty()) return;
        //入口
        //函数
        //出口
        return dfs(A,B,C,A.size());
    }
    void dfs
    (vector<int>& x,vector<int>& y,vector<int>& z,int n)
    {
        if(n==1)
        {
            z.push_back(x.back());
            x.pop_back();
            return;
        }
        dfs(x,z,y,n-1);
        z.push_back(x.back());
        x.pop_back();
        dfs(y,x,z,n-1);
    }
};  

我们可以画一下递归展开图来验证一下

[OS with AI_1 ] 计算机：无情的执行指令的机器 | 工具
在上面 操作系统的学习实验中，我们也尝试了借助栈，来非递归的解决汉诺塔问题，有兴趣的读者可以自己看看~