# 211 - 329 矩阵中的最长递增路径

## 题目

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

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

示例 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]。注意不允许在对角线方向上移动。

## 解答

> [https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/78308/15ms-Concise-Java-Solution](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/78308/15ms-Concise-Java-Solution)

每个格子查深度优先，上下左右看看有没有更大的数字

然后拿个小本本记一下，每个格子最多能走多远

```python
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        M, N = len(matrix), len(matrix[0])
        dp = [[0]*N for i in range(M)]

        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1+max(
                    dfs(i-1, j) if i and val > matrix[i-1][j] else 0,
                    dfs(i+1, j)if i < M-1 and val > matrix[i+1][j] else 0,
                    dfs(i, j-1)if j and val > matrix[i][j-1] else 0,
                    dfs(i, j+1)if j < N-1 and val > matrix[i][j+1] else 0,
                )
            return dp[i][j]
        return max(dfs(x, y) for x in range(M) for y in range(N))
```

> Runtime: 376 ms, faster than 94.19% of Python3 online submissions for Longest Increasing Path in a Matrix.
>
> Memory Usage: 13.2 MB, less than 100.00% of Python3 online submissions for Longest Increasing Path in a Matrix.
>
> [https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/dfsji-chong-xie-fa-by-powcai/](https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/dfsji-chong-xie-fa-by-powcai/)

这个版本更好理解

```python
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        row, col = len(matrix), len(matrix[0])
        dp = [[0]*col for i in range(row)]

        def dfs(i, j):
            if dp[i][j] != 0:
                return dp[i][j]
            res = 1
            for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                tmp_i = x+i
                tmp_j = y+j
                if tmp_i >= 0 and tmp_i < row and tmp_j >= 0 and tmp_j < col and \
                        matrix[tmp_i][tmp_j] > matrix[i][j]:
                    res = max(res, 1+dfs(tmp_i, tmp_j))
            dp[i][j] = max(res, dp[i][j])
            return dp[i][j]
        return max(dfs(x, y) for x in range(row) for y in range(col))
```

> Runtime: 892 ms, faster than 5.10% of Python3 online submissions for Longest Increasing Path in a Matrix.
>
> Memory Usage: 13.4 MB, less than 92.31% of Python3 online submissions for Longest Increasing Path in a Matrix.
