【记忆化搜索】329. 矩阵中的最长递增路径——理解记忆化搜索的原理

【记忆化搜索】329. 矩阵中的最长递增路径——思路分析

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出：4

解释：最长递增路径为 [1, 2, 6, 9]。

这道题的常规解法是使用DFS算法，然而当该算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，复杂度相当高了已经，当我上传代码时，果不其然……超时了……

class Solution {
public:
    int directions[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> board;
    int dfs(int r,int c,int last_num,int len){
        // cout<<len<<endl;
        int maxlen = len;
        for(int i = 0;i<4;i++){
            int new_r = r + directions[i][0];
            int new_c = c + directions[i][1];
            if(new_c>=0 && new_r>=0 && new_r<board.size() && new_c<board[0].size() && board[new_r][new_c] > last_num){
                maxlen = max(dfs(new_r,new_c,board[new_r][new_c],len+1),maxlen);
            }
        }
        return maxlen;

    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        board = matrix;
        vector<vector<int>> visited(matrix.size(),vector<int>(matrix[0].size(),0));
        int ans = 0;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[i].size();j++){
                // cout<<dfs(visited,i,j,matrix[i][j],1)<<endl;
                ans = max(ans,dfs(i,j,matrix[i][j],1));
            }
        }
        return ans;
    }
};
           

那么，也就要求我们必须进行优化，而优化的策略就是使用记忆化搜索（我之前没学过……据说这是记忆化搜索模板题……）

看了半天的题解，没人说啥是记忆化搜索，到底是怎么运行的，终于让我找到了一个说的明白的人，下面进入正题！！！

记忆化搜索

在普通的DFS中，对于同一个位置如果我们访问多次的话，则需要计算多次，比如说从 1 − 2 − 4 − 7 − 9 1-2-4-7-9 1−2−4−7−9和从 3 − 5 − 7 − 9 3-5-7-9 3−5−7−9这两条路径中从7出发所对应的最长路径需要计算两次，显然这是无效的，也是需要我们优化的地方。

如果我们设置一个二维数组，每次都记录对应点所能经过的最长路径长度，那么如果被重复经过该点的话就可以直接调用值即可。

说道这如果还没明白就看下面的这个例子：

如上图所示，最长路径应该是红色连接的点，但是在进行DFS过程中，需要对每个起点进行遍历，假如从5又开始遍历了一次，起点5对应的最长路径为蓝色部分

我们可以发现，7、9、13又被计数了一次，通过观察我们发现，从7出发的最长路径只有7-9-13，对应的长度应该是3，那么等下次如果又有一个路线走到了7，我们可以直接返回3啊，不用把后面的都跑一遍，这就是记忆化搜索！！！！

在这道题目中，就是利用的这样的一种思想，从而将时间复杂度从 O ( n 2 ) O(n^2) O(n2)降至 O ( m n ) O(mn) O(mn)，主要的做法是使用一个数组时刻记录着每个点所对应的最长路径长度，一旦走到该点则直接返回结果值。

使用数学语言描述如下：

f [ i ] [ j ] f[i][j] f[i][j]表示从 ( i , j ) (i,j) (i,j)出发的最长路径长度值

则：

f [ i ] [ j ] = m a x ( f [ x ] [ y ] ) , ( x , y ) 为 ( i , j ) 的 四 周 的 邻 点 f[i][j]=max(f[x][y]),(x,y)为(i,j)的四周的邻点 f[i][j]=max(f[x][y]),(x,y)为(i,j)的四周的邻点

【代码如下】

class Solution {
public:
    int directions[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> board;
    vector<vector<int>> store;
    int dfs(int r,int c){
        if(store[r][c]){
            return store[r][c];
        }
        int maxlen = 1;
        for(int i = 0;i<4;i++){
            int new_r = r + directions[i][0];
            int new_c = c + directions[i][1];
            if(new_c>=0 && new_r>=0 && new_r<board.size() && new_c<board[0].size() && board[new_r][new_c] > board[r][c]){
                maxlen = max(dfs(new_r,new_c)+1,maxlen);
            }
        }
        store[r][c] = maxlen;
        return maxlen;

    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        board = matrix;
        vector<vector<int>> t(matrix.size(),vector<int>(matrix[0].size(),0));
        store = t;
        int ans = 0;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[i].size();j++){
                ans = max(ans,dfs(i,j));
            }
        }
        return ans;
    }
};