329. Longest Increasing Path in a Matrix.md

329. Longest Increasing Path in a Matrix

思路

给定一个二维矩阵，求矩阵中最长的递增路径。我们可以从尝试从每个位置出发进行DFS，计算出以每个位置为起始的最长递增路径，最后返回最长即可。注意到DFS会存在大量重复，所以我们需要开辟一个二维记忆数组cache，cache[i][j]表示以位置ij为起始的最长递增路径长度，初始为0。当我们进行DFS时，如果发现cache[i][j] > 0，说明之前已经计算过了，无需再进行计算，直接返回cache[i][j]即可。

C++

class Solution {
private:
    int m, n;
    vector<vector<int>>cache;
    int DFS(const vector<vector<int>>& matrix, int i, int j){
        if(cache[i][j] > 0) return cache[i][j];
        
        int sub_res = 0;
        if(i > 0 && matrix[i-1][j] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i-1, j));
        if(j > 0 && matrix[i][j-1] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i, j-1));
        if(i < m-1 && matrix[i+1][j] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i+1, j));
        if(j < n-1 && matrix[i][j+1] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i, j+1));
        
        cache[i][j] = 1 + sub_res;
        return cache[i][j];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        if(!m) return 0;
        n = matrix[0].size();
        
        cache = vector<vector<int>>(m, vector<int>(n, 0));
        int res = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                res = max(res, DFS(matrix, i, j));

        return res;
    }
};