题解 | #矩阵最长递增路径#

如何用递归搜索最大路径？

最大路径的起点并不知道，因此我们需要遍历矩阵中的每个元素为起点，然后递归寻找这个起点开始的最大路径长度。

如何保证路径中的单元格不重复？

• 由于路径的单元格不能重复，我们需要一个dp数组保存矩阵中每个元素为起点的最大路径长度。
• 如果矩阵中的某个单元格没有更新最大路径长度，我们就增加一更新这个单元格的路径长度，表示这个单元格访问过了。
• 后面会再从上下左右四个方向更新这个单元格出发的最大路径长度，而且后面单元格的路径长度也会使用到前面单元格的路径长度来更新。

感想

此题跟岛屿数量 思路类似，都是用深度优先遍历来搜索二维矩阵中的所有元素来得到最终结果。即先遍历矩阵中的每个元素，然后以这个元素为起点来对各个方向深度遍历，找到这个元素的答案，深度递归过程中要注意不要超过数组的边界。

参考

https://blog.nowcoder.net/n/cc034a49cd994552a671ec4d26ec2163?f=comment

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-21 10:01:54
 * @FilePath: BM61-矩阵最长递增路径.js
 * @Description: 
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */
function solve( matrix ) {
    // write code here
    let maxPath = -Infinity;
    const n = matrix.length;
    const m = matrix[0].length;
    const dp = Array.from(new Array(n), () => new Array(m).fill(0));  // 存放矩阵中以某个元素为起点时的最大路径长度
    const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];  // 上下左右4个方向
    const _dfs = (i, j, matrix, dp) => {
        if (dp[i][j] !== 0) {
            return dp[i][j];  // 说明当前的格子已经走过了，可以直接用这个格子保存好的最大路径
        }

        dp[i][j]++;  // 初始增加1，表示这个单元格访问过了，后面会更新最大长度

        for (let k = 0; k < 4; ++k) {
            const nextI = i + direction[k][0];
            const nextJ = j + direction[k][1];

            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m && matrix[i][j] < matrix[nextI][nextJ]) {
                dp[i][j] = Math.max(dp[i][j], _dfs(nextI, nextJ, matrix, dp)+1);  // 更新4个方向的路径中的最大路径长度
            }
        }

        return dp[i][j];
    }

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            maxPath = Math.max(maxPath, _dfs(i, j, matrix, dp));
        }
    }

    return maxPath;
}

module.exports = {
    solve : solve
};