递归练习八（记忆化搜索）

一、解题心得

记忆化搜索就是带着备忘录递归搜索。

函数体设计：进 dfs 后先看看要找的值是不是在备忘录里面存着，有就直接返回，没有再考虑递归出口和中间函数逻辑。

记忆化搜索和递归暴搜都没有很大的关系，而是和动态规划问题有很大联系。

之前递归的暴搜问题基本都是用中间值 tmp 来记录每一条路径过程中的值，然后从上往下到出口时更新一次答案。

但是记忆化搜索是根据之前递归出的值来更新这次递归的值，防止一个值重复计算导致超时。这个思路不就是动态规划问题中把值记录在 dp 表中，用前面的值更新后面的值。

所以记忆化搜索不可避免的一定会有返回值，这也是不同于暴搜的，因为暴搜的值会存在 tmp 不用刻意返回。

所以一定要注意思考记忆化搜索的问题一定一定不是从暴搜角度考虑，而是从动态规划问题考虑。二者是明显不同的代码和思考逻辑！！！！！！！

下面是同一道题的暴搜（超时）和记忆化搜索（思考逻辑类似dp）的代码对比：

329. 矩阵中的最长递增路径 - 力扣（LeetCode）

1、暴搜：

class Solution {
public:
    int ans = 0;
    int tmp = 0;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[201][201];
    int m, n;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                vis[i][j] = true;
                tmp++;
                dfs(i, j, matrix);
                vis[i][j] = false;
                tmp--;
            }
        }
        return ans;
    }
    void dfs(int x, int y, vector<vector<int>>& matrix)
    {
        ans = max(ans, tmp);
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a >= 0 && a < m && b >= 0 && b < n && vis[a][b] == false && matrix[x][y] < matrix[a][b])
            {
                tmp++;
                vis[a][b] = true;
                dfs(a, b, matrix);
                tmp--;
                vis[a][b] = false;
            }
        }
    }
};

2、记忆化搜索：

class Solution {
public:
    int ans = 0;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[201][201];
    int m, n;
    // 记忆化搜索优化：记录以特定位置开头的最长递增路径
    int memo[201][201];
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                ans = max(ans, dfs(i, j, matrix));
            }
        }
        return ans;
    }
    int dfs(int x, int y, vector<vector<int>>& matrix)
    {
        // 先查
        if(memo[x][y])
            return memo[x][y];
        // 边界+逻辑
        int ret = 1;
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a >= 0 && a < m && b >= 0 && b < n && matrix[x][y] < matrix[a][b])
                ret = max(ret, dfs(a, b, matrix) + 1);
        }
        memo[x][y] = ret;
        return memo[x][y];
    }
};

以下是动态规划和记忆化搜索的共性：

记忆化搜索	动态规划
dfs函数含义	确定状态表示
dfs函数体设计	推到状态转移方程
dfs函数出口	初始化
填备忘录顺序	填dp表顺序
dfs函数返回值	返回dp表中合适值