329.md

329. Longest Increasing Path in a Matrix

Leetcode link

解题思路

题目要求我们在 m * n 的矩阵中找出最长连续递增路径长度，且只能往上下左右走

这道题咋看之下只能用 dfs 针对每一个矩阵元素分别进行遍历，想当然这么做肯定 TLE

经过仔细观察我们不难发现，当前节点的最长连续递增路径长度（以下简称路径），等于它上下左右四个元素的最长路径 + 1

于是我们就可以用一个数组 dp 来保存计算过的元素路径，之后遇到直接返回就完事了

以下是代码思路：

1. 对矩阵的每一个元素都进行一次 dfs，将每次 dfs 的结果与当前结果比较，保留比较大的那个

2. 在 dfs 中，首先判断当前的元素在 dp 数组中是否存在路径，存在的话直接返回

3. 不存在的话则需要对它的上下左右四个方向节点进行判断：

   • 是否越界
   • 是否比当前元素大

4. 如果没有越界且比当前元素大，则对其进行 dfs

5. 最后将 dfs 的结果 +1 与当前路径做比较，保存比较长的路径

6. 更新 dp

C++

class Solution {
public:
    vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix[0].size(),
            n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        int res = 0;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                res = max(res, dfs(i, j, dp, matrix));
            }
        }
        return res;
    }
    
    int dfs(int i, int j, vector<vector<int>> &dp, vector<vector<int>> &matrix) {
        if(dp[i][j]) {
            return dp[i][j];
        }
        int m = matrix[0].size(),
            n = matrix.size();
        int path = 1;
        for(vector<int> dir: dirs) {
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || x >= n || y < 0 || y >= m || matrix[x][y] <= matrix[i][j]) {
                continue;
            }
            path = max(path, 1 + dfs(x, y, dp, matrix));
        }
        dp[i][j] = path;
        return path;
    }
};

Javascript

const dirs = [[0,1], [0,-1], [1,0], [-1,0]];
var longestIncreasingPath = function(matrix) {
    
    // dp[i][j]: 从 [i, j] 开始的最长递增路径
    let dp = new Array(matrix.length)
    for(let i=0;i<dp.length;i++) {
        dp[i] = new Array(matrix[0].length).fill(0);
    }
    let res = 0;
    
    for(let i=0;i<matrix.length;i++) {
        for(let j=0;j<matrix[0].length;j++) {
            res = Math.max(res, dfs(i, j, dp, matrix));
        }
    }
    
    return res;
};

var dfs = function(i, j, dp, matrix) {
    if(dp[i][j] !== 0) {
        return dp[i][j];
    }
    let path = 1;
    let n = matrix.length, m = matrix[0].length;
    for(let dir of dirs) {
        let x = i + dir[0],
            y = j + dir[1];
        if(x >= n || x < 0 || y < 0 || y >= m || matrix[x][y] <= matrix[i][j] ) {
            continue;
        }
        path = Math.max(path, 1 + dfs(x, y, dp, matrix));
    }
    dp[i][j] = path;
    return path
}