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

问题：

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

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

示例 1：

[1, 2, 6, 9]

示例 2：

[3, 4, 5, 6]

示例 3：

输入：matrix = [[1]]
输出：1

回答：

var longestIncreasingPath = function(matrix) {
    let row = matrix.length;
    let col = matrix[0].length;
    let max = 0;
    let memo = new Array(row).fill().map(() => {
        return new Array(col).fill(0);
    })
    var dfs = function(i, j, prev) {
        
        if (i < 0 || j < 0 || i >= row || j >= col) {
            return 0;
        }
        if ((matrix[i][j] <= prev) || matrix[i][j] == -1) {
            return 0;
        }
        if (memo[i][j] > 0) {
            return memo[i][j]
        }
        let cur = matrix[i][j];
        let left = dfs(i, j - 1, cur);
        let right = dfs(i, j + 1, cur);
        let top = dfs(i - 1, j, cur);
        let bottom = dfs(i + 1, j, cur);
        memo[i][j] = Math.max(left, right, top, bottom) + 1;
        return memo[i][j];
    }
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            let res = dfs(i, j, -Infinity);
            max = Math.max(max, res)
        }
    }
    return max;
};