329. 矩阵中的最长递增路径

nice，有进步了，这是一道hard题目，而我自己写的，过了135/138个测试用例，没过的是因为超时了,说明不够优化

题目

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

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

示例 1：

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

代码与解析

我一开始写的代码超时了，需要记录重复走过的地方，但是当我记录的时候用了布尔数组发现一点作用都没起到：

class Solution {
    int n, m, ans = 0;
    boolean[][] state;
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        state = new boolean[m + 10][n + 10];
        for(int i = 0;i < m;i ++) {
            for(int j = 0;j < n;j ++) {
                dfs(matrix, i, j, 0);
            }
        }
        return ans;
    }
    public void dfs(int[][] matrix, int x, int y, int nums) {
        if(!notArea(x, y))   return;
        nums ++;
        ans = Math.max(ans, nums);
        if(notArea(x + 1, y) && matrix[x + 1][y] > matrix[x][y]) dfs(matrix, x + 1, y, nums);
        if(notArea(x - 1, y) && matrix[x - 1][y] > matrix[x][y]) dfs(matrix, x - 1, y, nums);
        if(notArea(x, y + 1) && matrix[x][y + 1] > matrix[x][y]) dfs(matrix, x, y + 1, nums);
        if(notArea(x, y - 1) && matrix[x][y - 1] > matrix[x][y]) dfs(matrix, x, y - 1, nums);

    }
    public boolean notArea(int x, int y) {
        if(x < 0 || y < 0 || x >= m || y >= n) return false;
        return true;
    }
}

然后问了下chatgpt如何优化我的代码，它提出了采用记忆化搜索的方式，记录已经访问过的位置的最长递增路径长度，记忆数组memo

class Solution {
    int m, n;
    int[][] memo; // 记忆数组

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(matrix, i, j, Integer.MIN_VALUE)); // 对每个点进行深度优先搜索
            }
        }

        return ans;
    }

    public int dfs(int[][] matrix, int x, int y, int prev) {
        if (x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] <= prev) {
            return 0; // 超出边界或者不满足递增条件，返回长度为0
        }
        if (memo[x][y] != 0) {
            return memo[x][y]; // 如果已经计算过该位置，直接返回其结果
        }

        int cur = matrix[x][y]; // 当前位置的值
        int pathLen = 0; // 记录当前路径的长度

        // 搜索当前位置的上下左右节点
        pathLen = Math.max(pathLen, dfs(matrix, x + 1, y, cur));
        pathLen = Math.max(pathLen, dfs(matrix, x - 1, y, cur));
        pathLen = Math.max(pathLen, dfs(matrix, x, y + 1, cur));
        pathLen = Math.max(pathLen, dfs(matrix, x, y - 1, cur));

        memo[x][y] = pathLen + 1; // 记录当前位置的最长递增路径长度
        return pathLen + 1;
    }
}

在深度优先搜索时，如果遇到已经计算过的位置，则直接返回其结果，避免了重复计算。这种方式可以避免超时情况，提高了效率。