☹️longest increasing path in matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

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

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;
    }
}

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

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;
    }
}