# longest increasing path in matrix

仍然是记忆化搜索，同时注意这道题不能用visited，比如前面一个cell visited了某个cell但是并没有采纳，如果你加进去的话就会造成其他cell想尝试也走不了，那么如何确保不会走回头路呢，很简单，我们用了记忆化搜索，探索过的cell会立刻返回值

```java
class Solution {
    Map<String, Integer> map = new HashMap<>();
    int[][] DIR = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int longestIncreasingPath(int[][] matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ans = Math.max(ans, dfs(matrix, i, j));
            }
        }
        return ans;
    }
    private int dfs(int[][] matrix, int i, int j) {
        String res = i + " " + j;
        if (map.containsKey(res)) {
            return map.get(res);
        }
        int ans = 1;
        for (int[] dir : DIR) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0)
                continue;
            if (matrix[x][y] <= matrix[i][j])
                continue;
            ans = Math.max(ans, dfs(matrix, x, y) + 1);
        }
        map.put(res, ans);
        return ans;
    }
}
```

如果你觉得想不通非得要用，那你就吃了吐

```java
class Solution {
    Map<String, Integer> map = new HashMap<>();
    int[][] DIR = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int longestIncreasingPath(int[][] matrix) {
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ans = Math.max(ans, dfs(matrix, i, j, new HashSet<>()));
            }
        }
        return ans;
    }
    private int dfs(int[][] matrix, int i, int j, Set<String> visited) {
        String res = i + " " + j;
        if (visited.contains(res)) 
            return -1;
        if (map.containsKey(res)) {
            return map.get(res);
        }
        int ans = 1;
        for (int[] dir : DIR) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0)
                continue;
            if (matrix[x][y] <= matrix[i][j])
                continue;
            visited.add(res);
            ans = Math.max(ans, dfs(matrix, x, y, visited) + 1);
            visited.remove(res);
        }
        map.put(res, ans);
        // System.out.println(res + " " + ans);
        return ans;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hzhang.gitbook.io/leetcode-record/dfs-backtracking/longest-increasing-path-in-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.