你现在需要用 C++ 实现 LeetCode 329 题「矩阵中的最长递增路径」，核心是编写 int longestIncreasingPath(vector<vector<int>>& matrix) 函数，找到矩阵中严格递增的最长路径长度。

解题思路

C++ 版本的实现核心依然是 深度优先搜索（DFS）+ 记忆化缓存，和之前的 Java/TypeScript/Python 逻辑一致，仅适配 C++ 语法特性：

1. 暴力DFS问题：直接递归每个格子会重复计算大量子路径，时间复杂度 O((mn)²)，效率极低。
2. 记忆化优化：用二维数组（vector）memo 缓存每个位置的最长递增路径长度，计算过的位置直接返回结果，时间复杂度优化到 O(mn)。
3. DFS逻辑：对当前位置，向上下左右四个方向探索，仅走「值更大」的格子，当前位置的最长路径 = 1（自身） + 所有有效方向的最大路径长度。

完整 C++ 实现

#include <vector>
#include <algorithm> // 用于 max 函数
using namespace std;

class Solution {
private:
    // 四个移动方向：上、下、左、右
    vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows;
    int cols;
    vector<vector<int>> memo; // 记忆化缓存，memo[i][j] 表示从(i,j)出发的最长递增路径长度

    // 深度优先搜索：计算从(i,j)出发的最长递增路径长度
    int dfs(vector<vector<int>>& matrix, int i, int j) {
        // 记忆化缓存：已计算过则直接返回结果
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        int max_len = 1; // 至少包含自身，长度为1
        // 遍历四个方向
        for (auto& dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            // 检查边界合法性 + 下一个值严格大于当前值
            if (x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > matrix[i][j]) {
                // 递归计算子路径长度，当前路径长度 = 1 + 子路径长度
                int len = 1 + dfs(matrix, x, y);
                max_len = max(max_len, len);
            }
        }

        // 将结果存入缓存，避免重复计算
        memo[i][j] = max_len;
        return max_len;
    }

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        // 边界条件：空矩阵处理
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }

        rows = matrix.size();
        cols = matrix[0].size();
        // 初始化记忆化缓存：和矩阵同尺寸，初始值为0（未计算）
        memo = vector<vector<int>>(rows, vector<int>(cols, 0));

        int max_length = 0;
        // 遍历矩阵所有位置，计算每个位置的最长路径
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                max_length = max(max_length, dfs(matrix, i, j));
            }
        }

        return max_length;
    }
};

代码关键解释

1. 方向数组：directions 用 vector<vector<int>> 定义，存储上下左右四个方向的偏移量，符合 C++ 容器使用习惯。
2. 记忆化缓存 memo：
   • 类型为 vector<vector<int>>，尺寸和输入矩阵一致，初始值为 0（表示该位置未被计算）。
   • 计算完某个位置的最长路径后，将结果存入 memo[i][j]，后续递归到该位置时直接返回，避免重复计算。
3. DFS 成员函数：
   • 作为 Solution 类的私有成员函数，直接访问类的成员变量 rows、cols、directions、memo，减少参数传递。
   • 核心逻辑：遍历四个方向，仅处理「边界合法（x >= 0 && x < rows && y >= 0 && y < cols）+ 值严格递增」的方向，递归计算子路径长度并取最大值。
4. 主逻辑：
   • 先判断矩阵是否为空（matrix.empty() || matrix[0].empty()），避免访问空容器导致崩溃。
   • 双重循环遍历矩阵所有位置，调用 DFS 计算每个位置的最长路径，最终返回全局最大值。

测试示例

// 测试代码
#include <iostream>
int main() {
    Solution sol;
    vector<vector<int>> matrix = {
        {9,9,4},
        {6,6,8},
        {2,1,1}
    };
    cout << sol.longestIncreasingPath(matrix) << endl; // 输出：4
    return 0;
}

路径说明：最长路径为 1 → 2 → 6 → 9（从 (2,1) 到 (0,0)），长度为 4。

总结

1. 核心优化：「记忆化 DFS」是解题关键，将时间复杂度从 O((mn)²) 优化到 O(mn)，是本题的最优解法。
2. C++ 特性适配：
   • 使用 vector 容器替代原生数组，更安全且适配 LeetCode 输入输出规范。
   • 成员函数封装 DFS 逻辑，减少全局变量使用，符合面向对象编程习惯。
3. 边界处理：严格判断矩阵是否为空、坐标是否越界，避免空指针/数组越界等运行时错误。