LeetCode 最长递增路径题解

LeetCode 最长递增路径题解题目描述给定一个 m x n 的整数矩阵找到最长递增路径的长度。示例输入matrix [[9,9,4],[6,6,8],[2,1,1]]输出4解题思路方法动态规划 DFS思路使用动态规划和 DFS。dp[i][j] 表示从 (i,j) 出发的最长递增路径长度。遍历所有起点计算最长递增路径长度。复杂度分析时间复杂度O(m * n)。空间复杂度O(m * n)。代码实现def longest_increasing_path(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) dp [[0] * n for _ in range(m)] directions [(0, 1), (0, -1), (1, 0), (-1, 0)] def dfs(i, j): if dp[i][j]: return dp[i][j] dp[i][j] 1 for di, dj in directions: ni, nj i di, j dj if 0 ni m and 0 nj n and matrix[ni][nj] matrix[i][j]: dp[i][j] max(dp[i][j], dfs(ni, nj) 1) return dp[i][j] return max(dfs(i, j) for i in range(m) for j in range(n)) # 测试 def test_longest_increasing_path(): matrix [[9, 9, 4], [6, 6, 8], [2, 1, 1]] print(longest_increasing_path(matrix)) # 输出4 if __name__ __main__: test_longest_increasing_path()总结最长递增路径是动态规划和 DFS 的典型应用通过 dp 数组存储每个点的最长递增路径长度。