思路

为了找到矩阵中的最长递增路径，可以使用动态规划和深度优先搜索（DFS）相结合的方法。

具体步骤如下：

  1. 初始化数据结构：创建一个与矩阵同样大小的二维数组，用于记录每个单元格的最长路径长度。
  2. 深度优先搜索：从每个单元格出发，递归地搜索其上下左右四个方向，更新最长路径长度。
  3. 动态规划：利用已经计算过的结果，避免重复计算，提高效率。
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self, matrix: List[List[int]]) -> int:
        # write code here
        if not matrix or not matrix[0]:#空单元格
            return 0
        m, n = len(matrix), len(matrix[0])#长度与宽带
        dp = [[0] * n for _ in range(m)]#记录单元格最长递增路径长度的二位列表
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]#上下左右四个方向

        def dfs(x, y):#通过dfs寻找当前单元格的最长递增路径长度
            if dp[x][y] != 0:#当前单元格已经被计算过，直接返回
                return dp[x][y]
            maxlen = 1#默认长度位1
            for dx, dy in directions:#查看当前节点及四周节点
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                    maxlen = max(maxlen, 1 + dfs(nx, ny))
            dp[x][y] = maxlen#当前节点最长递增路径
            return maxlen#返回最长递增路径

        return max(dfs(x,y) for x in range(m) for y in range(n))#返回所有单元格的最长递增路径

解释

  1. 初始化：创建一个与输入矩阵同样大小的二维数组 dp，用于记录每个单元格的最长路径长度。
  2. DFS函数：定义一个递归函数 dfs，从当前单元格出发，搜索其上下左右四个方向，更新最长路径长度。
  3. 动态规划：利用已经计算过的结果，避免重复计算，提高效率。

通过这种方法，可以高效地找到矩阵中的最长递增路径。