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

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

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

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/

这个版本更好理解

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.