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

[xxleyi]

解：

给定一个整数矩阵，找出最长递增路径的长度。

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

示例 1:

输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
示例 2:

输入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解 ：

经过几次深度遍历的练习，现在做这类题目能独立完成了，只是速度上不够快。需要花些时间调试代码才能成功提交。

此题在正确理解题意的基础上，可使用深度递归遍历加记忆化解决。多出的一点东西可能是需要对整个矩阵进行遍历式的深度递归遍历。这也可以直接整合到递归函数中。

var longestIncreasingPath = function(matrix) {
  // 处理退化情况
  if (matrix.length === 0) return 0

  // 初始化「循环不变式」相关的变量 cache。在此题中记忆化的作用更显著。
  let [rowNum, colNum] = [matrix.length, matrix[0].length]
  let cache = Array(rowNum)
  for (let i = 0; i < rowNum; i++) cache[i] = Array(colNum).fill(0)

  // 辅助方向变量
  let dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]
  // 辅助函数，判断坐标是否有效
  let valid =  (ni, nj) => ni >= 0 && ni < rowNum && nj >= 0 && nj < colNum

  // 用于存储答案的变量
  let pathLength = 0

  // 自带循环的深度递归遍历
  function dfsWithLoop (i = 0, j = 0) {
    // 命中缓存
    if (cache[i][j]) return

    let subPathLengths = [0]
    // 遍历所有子路径的最长递增路径的长度
    for (let [di, dj] of dir) {
      let ni = i + di, nj = j + dj
      if (valid(ni, nj) && matrix[ni][nj] > matrix[i][j]) {
        // 深度遍历
        dfsWithLoop(ni, nj)
        subPathLengths.push(cache[ni][nj])
      }
    }

    // 更新当前路径的最长递增路径的长度
    subPathLengths.sort((a, b) => b - a)
    cache[i][j] = 1 + subPathLengths[0]
    // 更新问题的解
    pathLength = Math.max(pathLength, cache[i][j])

    // 下一个深度遍历
    if (j < colNum - 1) dfsWithLoop(i, j + 1)
    else if (i < rowNum - 1) dfsWithLoop(i + 1, 0)

    // 深度遍历到底，返回
  }

  dfsWithLoop()
  return pathLength
};