【记忆化搜索】记忆化搜索算法的对比及总结

509. 斐波那契数

509. 斐波那契数

​ 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

​ 给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

解法一：递归

​ 在讲记忆化搜索之前，先来尝试用递归解决这道斐波那契数，其实我们前面已经遇见很多次斐波那契数了，现在还拿它出来讲，其实是因为它涉及到很多算法，比如递归、循环、动态规划、记忆化搜索、矩阵快速幂等等。

​ 所以这道题可以说是这些算法的入门题，我们不仅仅是要解决这道题，还要能从这道题看到这些算法的本质，所以不要觉得这道题太简单怎么怎么样！

​ 首先根据题目给的递推式，我们可以画出其递归树，假设 n=5，则递归树如下所示：

​ 根据之前我们学的递归步骤，可以快速地写出其代码，如下所示：

class Solution {
public:
    int fib(int n) {
        // 调用递归函数帮我们去解决问题，要相信dfs函数能帮我们返回其斐波那契数
        return dfs(n); 
    }

    int dfs(int n)
    {
        // 递归函数出口
        if(n == 0 || n == 1)
            return n;
        
        return dfs(n - 1) + dfs(n - 2);
    }
};

解法二：记忆化搜索💥

​ 其实我们可以看到上面递归树的一些问题，就是递归树中存在大量重复的节点，而这些节点都会去重复的遍历，导致时间上的消耗是很大的，因为一旦 n 越大，这个重复的节点就会越多，所以我们就要对其进行优化！

​ 仔细一想，我们只需要规避已经遍历过的子树，就能减少很多不必要的递归啦，那么要想知道已经遍历过哪些节点，就 可以使用一个 ”备忘录“ 记录下之前遍历过的节点，这样子一来后面遇到了重复的节点后只需要判断 ”备忘录“ 中是否已经出现过，就能规避到不必要的递归！

​ 而上面所说的操作，其实就叫做记忆化搜索！不要把它想得很复杂，其实 就是一个带 ”备忘录“ 的递归！

下面给出实现记忆化搜索的大概思路：

1. 创建一个备忘录，并且进行初始化~
2. 在递归返回的时候，将结果添加到备忘录中~
3. 在每次进入递归函数的时候，往备忘录里瞅一瞅~

​ 对于创建一个备忘录的操作，其实是有一个统一的思路的，就是按照 <可变参数，返回值> 的格式去创建！

​ 比如说这道斐波那契数中一直在变化的参数就是 n，它是 int 类型的；而返回值也是 int 类型，所以此时我们就构建一个 <int, int> 类型格式的备忘录！并且我们可以不用哈希表，而直接用一个数组来构建备忘录即可，因为可以让数组的下标作为 key，让数组的元素值作为对应的 value！

​ 还有一个要注意的点，就是 备忘录要初始化为递归中不出现的结果值，道理很容易懂，如果初始化的时候出现了可能出现的结果的话，那么在进入递归函数判断备忘录的时候就不会进入该结果的子树，就漏了该结果了！

​ 其它的步骤就比较简单了，就是在原来的递归操作上添加一些细节，如下所示：

class Solution {
private:
    int memory[31]; // 备忘录
public:
    int fib(int n) {
        memset(memory, -1, sizeof memory); // 初始化为不存在该结果值的数值
        return dfs(n);
    }

    int dfs(int n)
    {
        // 先判断是否已经遍历过该子树，是的话直接返回前面得到的结果即可
        if(memory[n] != -1)
            return memory[n];

        // 递归函数出口
        if(n == 0 || n == 1)
        {
            memory[n] = n; // 别忘了要添加到备忘录
            return n;
        }
        
        memory[n] = dfs(n - 1) + dfs(n - 2); // 别忘了要添加到备忘录
        return memory[n];
    }
};

3、动态规划 & 记忆化搜索 & 递归 的关系💥

​ 这道题使用动态规划同样能解决问题，并且，我们可以直接通过上面的递归函数以及记忆化搜索得出动态规划的步骤，因为其实它们都是一一对应的，如下图所示：

​ 根据这些步骤，我们能快速得到动态规划解决问题的代码：

class Solution {
public:
    int fib(int n) {
        // 1. 确定状态表示以及初始化
        vector<int> dp(31, 0); 
        dp[0] = 0, dp[1] = 1;
        
        // 2. 根据状态转移方程进行填表
        for(int i = 2; i <= n; ++i)
            dp[i] = dp[i - 1] + dp[i - 2];
        
        // 3. 返回结果
        return dp[n];
    }
};

​ 通过上面的例子，我们很容易发现，其实 动态规划、记忆化搜索、带备忘录的递归，它们是同一个东西！无非就是对暴力搜索的一些小优化，就是多了一个备忘录来保存前面的状态，但是它们 本质都还是暴力搜索！

☢️总结

1. 记忆化搜索就是一个带 ”备忘录“ 的递归（暴搜、深搜）。
2. 动态规划、记忆化搜索、带备忘录的递归，本质都是同一个东西，本质都还是暴力搜索，只不过做了优化！
3. 不是所有的递归都能转化为记忆化搜索的，记忆化搜索只适用于出现了大量重复的问题！
4. 递归和记忆化搜索，为动态规划解题又多开辟了一条思路，我们可以通过递归和记忆化搜索，想办法转化为动态规划！但并不是所有问题根据这样子转化都会很方便，有可能常规的动态规划（也就是我们前面学的动态规划五部曲）更方便，这都是因人而异，因题而异的！