LeetCode 第329题：矩阵中的最长递增路径

📖 文章摘要

本文详细解析LeetCode第329题“矩阵中的最长递增路径”，这是一道困难级别的动态规划和深度优先搜索问题。文章提供了记忆化DFS和动态规划两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升高级算法应用能力的程序员。

核心知识点： 动态规划、深度优先搜索、记忆化搜索
难度等级： 困难
推荐人群： 具有扎实算法基础，想要提升高级算法应用能力的程序员

题目描述

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

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

示例

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。

示例1

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例2

示例 3：

输入：matrix = [[1]]
输出：1

提示

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

解题思路

方法一：记忆化DFS

使用深度优先搜索配合记忆化来避免重复计算。

关键点：

使用记忆化数组存储已计算的结果
四个方向的DFS搜索
处理边界条件
递增路径的判断

具体步骤：

创建记忆化数组
对每个单元格进行DFS搜索
在搜索过程中记录已计算的结果
返回最长路径长度

时间复杂度：O(mn) 空间复杂度：O(mn)

方法二：动态规划

将问题转化为动态规划，使用拓扑排序的思想。

关键点：

计算每个单元格的出度
从出度为0的单元格开始更新
动态更新最长路径长度
使用队列优化更新过程

具体步骤：

计算每个单元格的出度
将出度为0的单元格入队
使用BFS更新最长路径
返回最大路径长度

时间复杂度：O(mn) 空间复杂度：O(mn)

图解思路

DFS搜索过程表

位置	当前值	可移动方向	路径长度
(0,0)	9	下	1
(1,0)	6	下	2
(2,0)	2	右	3
(2,1)	1	无	4

动态规划更新表

迭代次数	当前处理的单元格	更新的最长路径	剩余出度为0的单元格
1	(2,2)	1	(2,1)
2	(2,1)	2	(2,0)
3	(2,0)	3	(1,0)
4	(1,0)	4	(0,0)

代码实现

C# 实现

public class Solution {
    private int[,] memo;
    private int[][] directions = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0},
        new int[] {0, -1}, new int[] {0, 1}
    };
    
    public int LongestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }
        
        int m = matrix.Length;
        int n = matrix[0].Length;
        memo = new int[m,n];
        int maxLen = 0;
        
        // 对每个单元格进行DFS
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLen = Math.Max(maxLen, DFS(matrix, i, j));
            }
        }
        
        return maxLen;
    }
    
    private int DFS(int[][] matrix, int i, int j) {
        // 如果已经计算过，直接返回
        if (memo[i,j] != 0) {
            return memo[i,j];
        }
        
        // 初始长度为1
        memo[i,j] = 1;
        
        // 遍历四个方向
        foreach (var dir in directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            
            // 检查边界和递增条件
            if (newI >= 0 && newI < matrix.Length && 
                newJ >= 0 && newJ < matrix[0].Length && 
                matrix[newI][newJ] > matrix[i][j]) {
                memo[i,j] = Math.Max(memo[i,j], DFS(matrix, newI, newJ) + 1);
            }
        }
        
        return memo[i,j];
    }
}

Python 实现

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        def dfs(i: int, j: int) -> int:
            # 如果已经计算过，直接返回
            if memo[i][j] != 0:
                return memo[i][j]
            
            # 初始长度为1
            memo[i][j] = 1
            
            # 遍历四个方向
            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                new_i, new_j = i + di, j + dj
                
                # 检查边界和递增条件
                if (0 <= new_i < m and 0 <= new_j < n and 
                    matrix[new_i][new_j] > matrix[i][j]):
                    memo[i][j] = max(memo[i][j], dfs(new_i, new_j) + 1)
            
            return memo[i][j]
        
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for _ in range(m)]
        return max(dfs(i, j) for i in range(m) for j in range(n))

C++ 实现

class Solution {
private:
    vector<vector<int>> memo;
    vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    int dfs(vector<vector<int>>& matrix, int i, int j) {
        // 如果已经计算过，直接返回
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        
        // 初始长度为1
        memo[i][j] = 1;
        
        // 遍历四个方向
        for (const auto& dir : directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            
            // 检查边界和递增条件
            if (newI >= 0 && newI < matrix.size() && 
                newJ >= 0 && newJ < matrix[0].size() && 
                matrix[newI][newJ] > matrix[i][j]) {
                memo[i][j] = max(memo[i][j], dfs(matrix, newI, newJ) + 1);
            }
        }
        
        return memo[i][j];
    }
    
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }
        
        int m = matrix.size();
        int n = matrix[0].size();
        memo.resize(m, vector<int>(n, 0));
        
        int maxLen = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLen = max(maxLen, dfs(matrix, i, j));
            }
        }
        
        return maxLen;
    }
};

执行结果

C# 实现

执行用时：108 ms
内存消耗：40.2 MB

Python 实现

执行用时：324 ms
内存消耗：16.8 MB

C++ 实现

执行用时：36 ms
内存消耗：15.9 MB

性能对比

语言	执行用时	内存消耗	特点
C#	108 ms	40.2 MB	实现简洁，性能适中
Python	324 ms	16.8 MB	代码最简洁，但性能较差
C++	36 ms	15.9 MB	性能最优

代码亮点

🎯 使用记忆化搜索避免重复计算
💡 方向数组简化代码
🔍 完整的边界条件检查
🎨 代码结构清晰，模块化设计

常见错误分析

🚫 没有处理边界情况
🚫 递增条件判断错误
🚫 记忆化数组初始化错误
🚫 方向遍历不完整

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
记忆化DFS	O(mn)	O(mn)	实现简单	递归栈开销
动态规划	O(mn)	O(mn)	无递归开销	实现复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第329题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：记忆化DFS

方法二：动态规划

图解思路

DFS搜索过程表

动态规划更新表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流