矩阵中的最长递增路径Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

示例 1：

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

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入：matrix = [[1]]
输出：1

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2³¹ - 1

# 思路

dfs

# 解法


class Solution {
    
    int maxLen=0;
    public int longestIncreasingPath(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int[][]visited=new int[m][n];//计算以每个节点开头的递增序列的长度
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                maxLen=Math.max(maxLen,dfs(matrix,i,j,m,n,visited,Integer.MIN_VALUE));
            }
        }
        return maxLen;
    }
    public int dfs(int[][]matrix,int i,int j,int m,int n,int[][]visited,int pre){
        if(i<0||i>=m||j<0||j>=n||matrix[i][j]<=pre) return 0;
        if(visited[i][j]>0) return visited[i][j];//如果之前已经计算过，直接返回即可
        int l= dfs(matrix,i-1,j,m,n,visited,matrix[i][j]);
        int r= dfs(matrix,i+1,j,m,n,visited,matrix[i][j]);
        int up=dfs(matrix,i,j-1,m,n,visited,matrix[i][j]);
        int down=dfs(matrix,i,j+1,m,n,visited,matrix[i][j]);
        visited[i][j]=1+Math.max(Math.max(l,r),Math.max(up,down));
        return visited[i][j];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 总结

分析出几种情况，然后分别对各个情况实现