题解 | 矩阵最长递增路径

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int solve(vector<vector<int> >& matrix) {
        if (matrix.empty() || matrix[0].empty()) return  {};
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maxLength = max(maxLength, dfs(matrix, dp, i, j));
            }
        }
        return maxLength;
    }

  private:
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];

        int n = matrix.size();
        int m = matrix[0].size();
        int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int maxPath = 1;

        for (auto& dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]) {
                maxPath = max(maxPath, 1 + dfs(matrix, dp, x, y));
            }
        }

        dp[i][j] = maxPath;
        return maxPath;
    }
};

问题分析：需要在矩阵中找到一条严格递增的路径，每个格子只能访问一次，可以上下左右移动。

关键观察：对于每个单元格，其最长递增路径长度取决于其四个相邻单元格中值更大的那些单元格的路径长度。

算法选择：使用DFS遍历每个单元格，并通过记忆化存储已经计算过的结果，避免重复计算。

复杂度分析：每个单元格最多被处理一次，时间复杂度为O(nm)，空间复杂度为O(nm)用于存储记忆化结果。

代码解释：
1.初始化：检查矩阵是否为空，初始化一个与矩阵大小相同的dp数组用于记忆化，maxLength记录最终结果。
2.遍历每个单元格：对每个单元格调用DFS函数，计算从该单元格出发的最长递增路径长度，并更新maxLength。
3.DFS函数：
如果当前单元格的路径长度已经计算过（dp[i][j] != 0），直接返回该值。
否则，初始化maxPath为1（至少包含自身）。
遍历四个方向，检查相邻单元格是否满足递增条件，递归计算路径长度并更新maxPath。
将结果存储到dp数组中并返回。