最长递增路径（多解）_Java

给定一个整数矩阵，找出最长递增路径的长度。

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

示例 1:

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

示例 2:

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

解一，记忆化搜索

class Solution {
    int[][] dis;
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length==0) return 0;
        dis=new int[matrix.length][matrix[0].length];
        int ans=0;
        for(int i=0;i<matrix.length;++i){
            for(int j=0;j<matrix[i].length;++j){
                int x=find(i,j,matrix);
                if(x>ans)
                    ans=x;
            }
        }
        return ans;
    }
    public int find(int x,int y,int[][] map){
        if(dis[x][y]!=0){
            return dis[x][y];
        }else{
            int[] dx=new int[]{1,0,-1,0};
            int[] dy=new int[]{0,1,0,-1};
            int max=0;
            for(int i=0;i<dx.length;++i){
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(xx>=0&&xx<map.length&&yy>=0&&yy<map[0].length&&map[xx][yy]>map[x][y]){
                    int ans=find(xx,yy,map);
                    if(ans>max)
                        max=ans;
                }
            }
            return dis[x][y]=max+1;
        }
        
    }
}

思路简单直接，dfs+记忆数组就行了

解二，拓扑排序

class Solution {
    public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int rows, columns;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        rows = matrix.length;
        columns = matrix[0].length;
        int[][] outdegrees = new int[rows][columns];
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                for (int[] dir : dirs) {
                    int newRow = i + dir[0], newColumn = j + dir[1];
                    if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) {
                        ++outdegrees[i][j];
                    }
                }
            }
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (outdegrees[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            ++ans;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int[] cell = queue.poll();
                int row = cell[0], column = cell[1];
                for (int[] dir : dirs) {
                    int newRow = row + dir[0], newColumn = column + dir[1];
                    if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column]) {
                        --outdegrees[newRow][newColumn];
                        if (outdegrees[newRow][newColumn] == 0) {
                            queue.offer(new int[]{newRow, newColumn});
                        }
                    }
                }
            }
        }
        return ans;
    }
}

借助拓扑排序按层出队，则遍历的层数即是递增序列的最长长度

解三，动态规划

class Solution {
    class Node {
        int x;
        int y;
        int val;

        public Node(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }

    public int longestIncreasingPath(int[][] g) {
        if (g.length == 0) return 0;

        int n = g.length, m = g[0].length;

        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nodes.add(new Node(i, j, g[i][j]));
            }
        }

        nodes.sort((o1, o2) -> o1.val - o2.val);

        int[][] f = new int[n][m];
        for (int i = 0; i < n; i++) Arrays.fill(f[i], 1);

        int ans = 0;
        int[] dirs = {0, 1, 0, -1, 0};
        for (Node node : nodes) {
            int x = node.x;
            int y = node.y;
            int val = node.val;

            for (int i = 0; i < 4; i++) {
                int sx = x + dirs[i], sy = y + dirs[i + 1];
                if (0 <= sx && sx < n && 0 <= sy && sy < m && g[sx][sy] < val) {
                    f[x][y] = Math.max(f[x][y], f[sx][sy] + 1);
                }
            }
            ans = Math.max(ans, f[x][y]);
        }
        return ans;
    }
}

首先对图中的点集从大到小排序，那么按照排序进行状态转移时，小的数在后面，状态完全依赖于大的数，即可完成自底向上的动态规划。

本文地址：https://blog.csdn.net/qq_35513792/article/details/107589700