题解 | 矩阵最长递增路径

没看到有JavaScript的代码，贴一个在这里

思路：

• 用深度优先查找dfs
• dp是动态规划数组，便于在for循环中减少dfs次数

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */
function solve(matrix) {
    // write code here
    const mR = matrix.length;
    const mC = matrix[0].length;
    const steps = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
    ];
    const dp=new Array(mR).fill(0).map((_)=>new Array(mC).fill(0))
    let maxLen = 0;
    const dfs = (i, j) => {
        if(dp[i][j]>0) {
            return dp[i][j]
        }
        let maxPath=1
        for (let [r, c] of steps) {
            let curI = i + r;
            let curJ = j + c;
            if (
                curI >= 0 &&
                curI < mR &&
                curJ >= 0 &&
                curJ < mC &&
                matrix[curI][curJ] > matrix[i][j]
            ) {
                maxPath=Math.max(maxPath,1+dfs(curI,curJ))
            }
        }
        dp[i][j]=maxPath
        return dp[i][j]
    };
    for(let i=0;i<mR;i++){
        for(let j=0;j<mC;j++){
            maxLen=Math.max(maxLen,dfs(i,j))
        }
    }
    return maxLen
}
module.exports = {
    solve: solve,
};