专题五：记忆化搜索-CSDN博客

本文链接：https://blog.csdn.net/AAlykk/article/details/144269085

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是记忆化搜索，并且掌握记忆化搜索算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：递归、搜索与回溯算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

记忆化搜索（Memoization Search）：

是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。

主要特点和应用场景包括：

避免重复计算：记忆化搜索算法通过缓存已经计算过的结果，以避免对相同输入进行重复计算。这在递归算法中特别有用，因为递归往往会导致相同的子问题被反复解决。
提高效率：通过保存中间计算结果，记忆化搜索算法能够大幅减少算法的时间复杂度，从指数级别降低到多项式级别。

动态规划：

记忆化搜索在动态规划中经常被使用。动态规划是一种解决优化问题的方法，通常包含递归和子问题重叠的特点。记忆化搜索能够避免重复计算，使得动态规划算法更加高效。

递归算法优化：

记忆化搜索主要用于优化递归算法。在递归调用中，如果存在相同的输入参数，记忆化搜索算法将直接返回已经计算过的结果，而不是重新执行计算。

应用于搜索问题：

记忆化搜索不仅用于动态规划，还可以应用于搜索问题，特别是深度优先搜索中的状态记忆。

二、算法习题

2.1 第一题

题目链接：509. 斐波那契数 - 力扣（LeetCode）

题目描述：

算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个数 n ，返回第 n 个斐波那契数的值；
函数体：斐波那契数的递推公式；
递归出⼝：当 n == 0 或者 n == 1 时，不⽤套公式。

记忆化搜索：

加上⼀个备忘录；
每次进⼊递归的时候，去备忘录⾥⾯看看；
每次返回的时候，将结果加⼊到备忘录⾥⾯。

动态规划：

递归含义 -> 状态表⽰；
函数体 -> 状态转移⽅程；
递归出⼝ -> 初始化。

代码呈现：

class Solution {
public:
    int memo[31]; // memory 备忘录
    int dp[31];
    int fib(int n) 
    {
        // 动态规划
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
    // 记忆化搜索
    int dfs(int n) 
    {
        if (memo[n] != -1)
            return memo[n]; // 直接去备忘录⾥⾯拿值
        if (n == 0 || n == 1) {
            memo[n] = n; // 记录到备忘录⾥⾯
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n - 2); // 记录到备忘录⾥⾯
        return memo[n];
    }
};

2.2 第二题

题目链接：62. 不同路径 - 力扣（LeetCode）

题目描述：

算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个下标，返回从 [0, 0] 位置⾛到 [i, j] 位置⼀共有多少种⽅法；
函数体：只要知道到达上⾯位置的⽅法数以及到达左边位置的⽅法数，然后累加起来即可；
递归出⼝：当下标越界的时候返回 0 ；当位于起点的时候，返回 1 。

记忆化搜索：

加上⼀个备忘录；
每次进⼊递归的时候，去备忘录⾥⾯看看；
每次返回的时候，将结果加⼊到备忘录⾥⾯。

动态规划：

递归含义 -> 状态表⽰；
函数体 -> 状态转移⽅程；
递归出⼝ -> 初始化。

代码呈现：

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        // 动态规划
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) 
            {
                if (i == 1 && j == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        return dp[m][n];
        // 记忆化搜索
        // vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        // return dfs(m, n, memo);
    }
    int dfs(int i, int j, vector<vector<int>>& memo) 
    {
        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 1;
        }
        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }
};

2.3 第三题

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

题目描述：

算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个数 i ，返回以 i 位置为起点的最⻓递增⼦序列的⻓度；
函数体：遍历 i 后⾯的所有位置，看看谁能加到 i 这个元素的后⾯。统计所有情况下的最⼤值。
递归出⼝：因为我们是判断之后再进⼊递归的，因此没有出⼝~

记忆化搜索：

加上⼀个备忘录；
每次进⼊递归的时候，去备忘录⾥⾯看看；
每次返回的时候，将结果加⼊到备忘录⾥⾯。

动态规划：

递归含义 -> 状态表⽰；
函数体 -> 状态转移⽅程；
递归出⼝ -> 初始化。

代码呈现：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        // 动态规划
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 0;
        // 填表顺序：从后往前
        for (int i = n - 1; i >= 0; i--) 
        {
            for (int j = i + 1; j < n; j++) 
            {
                if (nums[j] > nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
        // 记忆化搜索
        //
        // vector<int> memo(n);
        // int ret = 0;
        // 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;
    }
};

2.4 第四题

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

题目描述：

算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个区间 [left, right] ，返回在这个区间上能完胜的最⼩费⽤；
函数体：选择 [left, right] 区间上的任意⼀个数作为头结点，然后递归分析左右⼦树。求出所有情况下的最⼩值；
递归出⼝：当 left >= right 的时候，直接返回 0 。

记忆化搜索：

加上⼀个备忘录；
每次进⼊递归的时候，去备忘录⾥⾯看看；
每次返回的时候，将结果加⼊到备忘录⾥⾯。

代码呈现：

class Solution {
    int memo[201][201];

public:
    int getMoneyAmount(int n) { return dfs(1, n); }
    int dfs(int left, int right) 
    {
        if (left >= right)
            return 0;
        if (memo[left][right] != 0)
            return memo[left][right];
        int ret = INT_MAX;
        for (int head = left; head <= right; head++) // 选择头结点
        {
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = min(ret, head + max(x, y));
        }
        memo[left][right] = ret;
        return ret;
    }
};

2.5 第五题

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

题目描述：

算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个下标 [i, j] ，返回从这个位置开始的最⻓递增路径的⻓度；
函数体：上下左右四个⽅向瞅⼀瞅，哪⾥能过去就过去，统计四个⽅向上的最⼤⻓度；
递归出⼝：因为我们是先判断再进⼊递归，因此没有出⼝~

记忆化搜索：

加上⼀个备忘录；
每次进⼊递归的时候，去备忘录⾥⾯看看；
每次返回的时候，将结果加⼊到备忘录⾥⾯。

代码呈现：

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

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ret = max(ret, dfs(matrix, i, j));
        return ret;
    }
    int dfs(vector<vector<int>>& matrix, int i, int j) 
    {
        if (memo[i][j] != 0)
            return memo[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++) 
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
                ret = max(ret, dfs(matrix, x, y) + 1);
        }
        memo[i][j] = ret;
        return ret;
    }
};