LeetCode 329：矩阵中的最长递增路径 — 逐步可视化追踪

Source: Dev.to

问题描述

找到矩阵中最长递增路径的长度，路径可以向四个方向（上、下、左、右）移动到相邻的严格递增的单元格。

方法

该解法使用深度优先搜索（DFS）结合记忆化：

1. 从每个单元格开始进行 DFS，探索所有可能的递增路径。
2. 将从每个单元格出发的最长路径长度存入 DP（记忆化）表，以避免重复计算。
3. 最终答案是 DP 表中所有起始位置的最大值。

复杂度分析

• 时间复杂度: O(m × n) – 由于记忆化，每个单元格只会被处理一次。
• 空间复杂度: O(m × n) – 用于 DP 表和递归栈。

参考实现（Python）

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        # Directions: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        m, n = len(matrix), len(matrix[0])
        dp = [[-1] * n for _ in range(m)]  # memoization table

        def dfs(i: int, j: int) -> int:
            # Return cached result if already computed
            if dp[i][j] != -1:
                return dp[i][j]

            # At least the cell itself
            dp[i][j] = 1

            # Explore neighbors
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    dp[i][j] = max(dp[i][j], 1 + dfs(x, y))

            return dp[i][j]

        max_path = 0
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))

        return max_path

交互式可视化

自己动手试试: Open TraceLit and step through every line – 该工具基于 TraceLit，提供 LeetCode 练习的可视化算法追踪。