首页 > 试题广场 >

矩阵最长递增路径

[编程题]矩阵最长递增路径

热度指数：52891 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。

2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围： $1 \le n,m \le 1000$ ， $0 \le matrix[i][j] \le 1000$

进阶：空间复杂度 $O(nm)$ ，时间复杂度 $O(nm)$

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，

其中的一条最长递增路径如下图所示：

示例1

输入

[[1,2,3],[4,5,6],[7,8,9]]

输出

说明

1->2->3->6->9即可。当然这种递增路径不是唯一的。

示例2

输入

[[1,2],[4,3]]

输出

说明

 1->2->3->4

备注:

矩阵的长和宽均不大于1000，矩阵内每个数不大于1000

算法知识视频讲解

Java

牛客839384289号

int res=0;
public int solve (int[][] matrix) {
    // write code here
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[i].length;j++){
            dfs(matrix , i ,j ,0 ,-1);
        }
    }
    return res;
}

public void dfs(int[][] matrix ,int m ,int n ,int cnt ,int val){
    // 满足m,n均在范围内，且当前值大于上一步的值，才可以继续累加（走回头路不满足递增，会马上被return掉）
    if(m<0 || m>=matrix.length || n<0 || n>=matrix[0].length || matrix[m][n]<=val){
        res=Math.max(res ,cnt);
        return;
    }
    cnt++;
    dfs(matrix ,m+1 ,n ,cnt ,matrix[m][n]);
    dfs(matrix ,m-1 ,n ,cnt ,matrix[m][n]);
    dfs(matrix ,m ,n+1 ,cnt ,matrix[m][n]);
    dfs(matrix ,m ,n-1 ,cnt ,matrix[m][n]);
}

编辑于 2024-03-17 13:23:37 回复(0)

Java

牛客225887487号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int maxPath = 0;

    public int solve (int[][] matrix) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                findPath(matrix, i, j, 0, -1);
            }
        }
        return maxPath;
    }

    void findPath (int[][] matrix, int i, int j, int num, int lastNum) {
        if (i < 0 || i >= matrix.length || j < 0
                || j>= matrix[0].length || matrix[i][j] <= lastNum) {
            maxPath = Math.max(maxPath, num);
            return;
        }
        ++ num;
        findPath(matrix, i + 1, j, num, matrix[i][j]);
        findPath(matrix, i, j + 1, num, matrix[i][j]);
        findPath(matrix, i - 1, j, num, matrix[i][j]);
        findPath(matrix, i, j - 1, num, matrix[i][j]);
    }
}

编辑于 2023-12-21 17:20:08 回复(0)

Java

做则必成的勇气和信心

int ans=0;
    public int solve (int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] used=new int[m][n];  //是否走过
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                build(matrix,i,j,-1,0);//此时，最长递增路径长度为0
            }
        }
        return ans;
    }
    public void build(int[][] matrix,int i,int j,int pre,int len){
        //递增，不包括等于
        int m=matrix.length;
        int n=matrix[0].length;
        if(i<0||j<0||i>=m||j>=n||matrix[i][j]<=pre){
            ans=Math.max(ans,len);
            return;
        }
        pre=matrix[i][j];
        build(matrix,i,j-1,pre,len+1);
        build(matrix,i,j+1,pre,len+1);
        build(matrix,i-1,j,pre,len+1);
        build(matrix,i+1,j,pre,len+1);
    }

发表于 2023-07-15 14:51:42 回复(0)

Java

Zhima1234

public class Solution {
    // 向上的向量
    private static final int[] UP = {-1, 0};
    // 向下的向量
    private static final int[] DOWN = {1, 0};
    // 向左的向量
    private static final int[] LEFT = {0, -1};
    // 向右的向量
    private static final int[] RIGHT = {0, 1};
    // 上下左右的向量
    private static final int[][] DIRECTIONS = {UP, DOWN, LEFT, RIGHT};
    // 最长递增路径
    int ans;
    public int solve (int[][] matrix) {
        ans = 0;
        boolean[][] path = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                path[i][j] = true;
                backTrack(matrix, i, j, 1, path);
                path[i][j] = false;
            }
        }
        return ans;
    }
    private void backTrack(int[][] matrix, int x, int y, int len,
                           boolean[][] path) {
        ans = Math.max(ans, len);
        for (int[] direction : DIRECTIONS) {
            int nX = direction[0] + x;
            int nY = direction[1] + y;
            // 越界了
            if (nX < 0 || nX >= matrix.length || nY < 0 || nY >= matrix[x].length) {
                continue;
            }
            // 不能走回头路
            if (path[nX][nY]) {
                continue;
            }
            // 不符合递增序列的要求
            if (matrix[nX][nY] <= matrix[x][y]) {
                continue;
            }
            path[nX][nY] = true;
            backTrack(matrix, nX, nY, len + 1, path);
            path[nX][nY] = false;
        }
    }
}

发表于 2023-05-30 22:14:51 回复(0)

Java

容容yuyu

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int max =0;
    int m;
    int n;
    int[][] matrix;
    public int solve (int[][] matrix) {
        this.matrix = matrix;
        if(matrix==null||matrix.length==0||matrix[0].length==0) return 0;
        this.m = matrix.length;
        this.n = matrix[0].length;
        for(int i=0;i<m;i++){
            for(int j =0;j<n;j++){
                backtraking(i,j,-1,0);
            }
        }
        return max;
        
    }

    public void backtraking(int i,int j,int pre,int len){
        if(i<0||i>=m||j<0||j>=n||matrix[i][j]<=pre){
            max = Math.max(max,len);
            return;
        }
        int temp = matrix[i][j];
        matrix[i][j]=-1;
        backtraking(i-1,j,temp,len+1);
        backtraking(i+1,j,temp,len+1);
        backtraking(i,j-1,temp,len+1);
        backtraking(i,j+1,temp,len+1);
        matrix[i][j]=temp;
    }
}

发表于 2023-03-02 23:01:13 回复(0)

Java

ludvig

//1.对于矩阵中的每个点，都把它作为起点开始遍历

//2.递归退出的条件有 a.达到矩阵边界 b.不满足递增

//3.设置状态矩阵，在递归的时候判断这个点来没来过，记得退出每层递归的时候都要把它恢复原状，因为你一条路线回退了，别的路线还得用你这个格子

public class Solution {

public int count;

public int solve (int[][] matrix) {

boolean[][] state = new boolean[matrix.length][matrix[0].length];

for (int k = 0; k < matrix.length; k++) {

for (int i = 0; i < matrix[0].length; i++) {

recursion(state, -1, matrix, k, i, 0);

}

return count;

}

public void recursion(boolean[][] state, int num, int[][] matrix, int i, int j,

int index) {

if (i < 0 || i >= matrix.length) {

return;

}

if (j < 0 || j >= matrix[0].length) {

return;

}

if (index > count) {

count = index;

}

if (num >= matrix[i][j]) {

return;

}

if (!state[i][j]) {

num = matrix[i][j];

state[i][j] = true;

recursion(state, num, matrix, i + 1, j, index + 1);

recursion(state, num, matrix, i - 1, j, index + 1);

recursion(state, num, matrix, i, j + 1, index + 1);

recursion(state, num, matrix, i, j - 1, index + 1);

state[i][j] = false;

}

发表于 2022-09-28 12:00:46 回复(0)

Java

offer多多_益_善

迷迷糊糊就过了，感觉还不是很懂，有些地方理解起来比较难

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型二维数组描述矩阵的每个数
* @return int整型
*/
int maxLen = 0;
public int solve (int[][] matrix) {
// write code here
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int maxRow = matrix.length;
int maxClo = matrix[0].length;
for (int i = 0; i < maxRow; i++) {
for (int j = 0; j < maxClo; j++) {
maxLen = Math.max(maxLen, helper(i, j, maxRow, maxClo, matrix, 1));
}
}
return maxLen;
}
// i表示当前元素的横坐标j表示纵坐标，value表示当前的值
private int helper(int i, int j, int maxRow, int maxClo, int[][] matrix,
int max) {
//往前走
if (j + 1 < maxClo && matrix[i][j + 1] > matrix[i][j]) {
maxLen = Math.max(max + 1, helper(i, j + 1, maxRow, maxClo, matrix, max + 1));
}
//往后走
if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
maxLen = Math.max(max + 1,helper(i, j - 1, maxRow, maxClo, matrix, max + 1));
}
//往上走
if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
maxLen = Math.max(max + 1, helper(i - 1, j, maxRow, maxClo, matrix, max + 1));
}
if (i + 1 < maxRow && matrix[i + 1][j] > matrix[i][j]) {
maxLen = Math.max(max + 1, helper(i + 1, j, maxRow, maxClo, matrix, max + 1));
}

return maxLen;
}
}

发表于 2022-09-16 19:09:36 回复(0)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
        ArrayList<Integer> list=new ArrayList<Integer>();

        for(int i=0;i<=matrix.length-1;i++){
            for(int j=0;j<=matrix[0].length-1;j++){
                boolean[][] used=new boolean[matrix.length][matrix[0].length];
                ArrayList<Integer> path=new ArrayList<Integer>();//path中存每个位置为起点的路径之一
                ArrayList<Integer> res=new ArrayList<Integer>();
                dfs(matrix,i,j,used,path,res);//res中存每个位置为起点的路径的所有长度
                list.add(max(res));//list中存每个位置为起点的路径的最大长度
            }
        }
        return max(list);
    }
    public void dfs(int[][] arr,int i,int j,boolean[][] used,ArrayList<Integer> path,ArrayList<Integer> res){
        if(!isArea(arr,i,j)){return;}//超出边界--回溯
        if(used[i][j]==true){return;}//已经用过--回溯
        if(!path.isEmpty()&&arr[i][j]<path.get(path.size()-1)){return;}//这一步比上一步小--回溯
       
        path.add(arr[i][j]);
        used[i][j]=true;//表示已经搜过了这里
        dfs(arr,i-1,j,used,path,res);
        dfs(arr,i+1,j,used,path,res);
        dfs(arr,i,j-1,used,path,res);
        dfs(arr,i,j+1,used,path,res);
        
        res.add(path.size());//res中放一个轮回中每条route的length
        
        path.remove(path.size()-1);
    }
    
    public boolean isArea(int[][] arr,int i,int j){
        return i>=0&&j>=0&&i<=arr.length-1&&j<=arr[0].length-1;
    }
    
    public int max(ArrayList<Integer> res){
        int max=res.get(0);
        for(int i=1;i<=res.size()-1;i++){
            if(res.get(i)>max){
                max=res.get(i);
            }
        }
        return max;
    }
}

发表于 2022-08-05 18:48:14 回复(0)

Java

624huiguorou

矩阵最长递增路径

dfs

通常dfs不是从0,0开始的，所以两个for里用dfs。

如果要算路径长度，dfs参数里设置个int，+1就可以统计长度。

直到边界结束，来记录最大长度。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    
    int res = 0;
    
    public int solve (int[][] matrix) {
        // write code here
        int r = matrix.length-1, c = matrix[0].length-1;
        //是否走过（length声明少了就加个1）
        int[][] a = new int[r+1][c+1];
        //不一定是从0,0开始，一般都不是从0.0开始，都需要对每个点进行搜索
        for(int i = 0; i <= r; i++){
            for(int j = 0; j <= c; j++){
                //c每次加1，记录路径长度
                dfs(matrix, i, j, -1, 0);
            }
        }
        return res;
    }
    
    //b是记录上一个的值
    public void dfs(int[][] matrix,  int i, int j, int b, int c){
        //dfs递归边界，超出二位边界，不满足大于条件
        if(i < 0 || i >= matrix.length || 
           j < 0 || j >= matrix[0].length ||
           matrix[i][j] <= b) {
            //当越界到最后时，才记录最大值
            res = Math.max(res, c);
            return;
        }
        //不论大不大，都是需要被改变的
        b = matrix[i][j];
        //dfs递归
        dfs(matrix, i, j-1, b, c+1);
        dfs(matrix, i, j+1, b, c+1);
        dfs(matrix, i+1, j, b, c+1);
        dfs(matrix, i-1, j, b, c+1);
    }
}

发表于 2022-07-29 00:08:57 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    int res = 0;
    public int solve (int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                bfs(matrix, i, j, 0, Integer.MIN_VALUE);
        return res;
    }
    public void bfs(int[][] matrix, int i, int j, int length, int pred){
        int m = matrix.length, n = matrix[0].length;
        if(i<0 || i>=m || j<0 || j>=n || matrix[i][j]<=pred) return;// 路径需要严格递增
        
        pred = matrix[i][j];
        length = length + 1;
        res = Math.max(length, res);
        bfs(matrix, i+1, j, length, pred);
        bfs(matrix, i-1, j, length, pred);
        bfs(matrix, i, j+1, length, pred); 
        bfs(matrix, i, j-1, length, pred);
    } 
}

发表于 2022-07-19 17:56:59 回复(0)

Java

沉默归来

dfs的记忆化搜索

public class Solution {
    int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
    public int solve (int[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0) return 0;
        int ans = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i=0;i<matrix.length;++i){
            for(int j=0;j<matrix[0].length;++j){
                ans = Math.max(ans,dfs(matrix,dp,i,j));
            }
        }
        return ans;
    }
    
    public int dfs(int[][] mat, int[][] dp, int i, int j){
        //记忆化搜索
        if(dp[i][j]!=0) return dp[i][j];
        for(int k=0;k<4;++k){
            int x = i+dx[k], y = j+dy[k];
            if((x>=0 && x<mat.length) && (y>=0 && y<mat[0].length) && mat[x][y]>mat[i][j]){
                //加1是该位置本身的长度
                dp[i][j]=Math.max(dp[i][j], dfs(mat,dp,x,y)+1);
            }
        }
        //如果到最后dp[i][j]的值都是0，说明该位置周围已经没有比它大的点了，最长递增路径为本身
        return dp[i][j]==0? 1:dp[i][j];
    }
}

发表于 2022-06-23 15:57:21 回复(0)

Java

刚炸的土豆

import java.util.*;
public class Solution {
    int [][] vis;
    int n;
    public int solve (int[][] matrix) {
        // write code here
        n=matrix.length;
        vis=new int[n][n];
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans=Math.max(ans,dfs(matrix,i,j,-1));
            }
        }
        return ans;
    }
    public int dfs(int[][] matrix,int i,int j,int pre){
        //访问过，或者越界返回0
        if(i<0||i>=n||j<0||j>=n||vis[i][j]==1){
            return 0;
        }
        //当前数小于前一个数，返回0
        if(matrix[i][j]<=pre){
            return 0;
        }
        int len=0;
        vis[i][j]=1;
        //dfs，取返回值最大值
        len=Math.max(dfs(matrix,i-1,j,matrix[i][j])+1,len);
        len=Math.max(dfs(matrix,i+1,j,matrix[i][j])+1,len);
        len=Math.max(dfs(matrix,i,j-1,matrix[i][j])+1,len);
        len=Math.max(dfs(matrix,i,j+1,matrix[i][j])+1,len);
        vis[i][j]=0;
        return len;
    }
}

发表于 2022-05-20 10:55:23 回复(0)

Java

univeralvv

import java.util.*;


public class Solution {
    int max = Integer.MIN_VALUE;
    public int solve (int[][] m) {
        int row = m.length;
        int col = m[0].length;
        boolean[][] visi = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                backTrack(m, i, j, visi, 0,Integer.MIN_VALUE);
            }
        }
        return max;
    }
    
    private void backTrack (int[][] m, int i, int j, boolean[][] visi , int l, int prev) {
        int row = m.length;
        int col = m[0].length;
        if (i < 0 || j < 0 || i >= row || j >= col) {
            return ;
        }
        if (prev >= m[i][j]) {
            return ;
        }
        if (visi[i][j] == false) {
            l++;
            visi[i][j] = true;
            if (l > max) {
                max = l;
            }
            backTrack(m, i+1, j, visi, l, m[i][j]);
            backTrack(m, i, j+1, visi, l, m[i][j]);
            backTrack(m, i-1, j, visi, l, m[i][j]);
            backTrack(m, i, j-1, visi, l, m[i][j]);
            visi[i][j] = false;
        }
    }
}

发表于 2022-05-12 21:46:42 回复(0)

Java

触初

import java.util.HashMap;
import java.util.HashSet;

/**
 * NC138 矩阵最长递增路径
 */
public class Solution138 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     *
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve(int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int max = 0;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == 0) {
                    max = Math.max(max, dfs(matrix, i, j, -1, dp, n, m));
                }
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int i, int j, int num, int[][] dp, int n, int m) {
        if (i < 0 || i >= n || j < 0 || j >= m || matrix[i][j] <= num) {
            return 0;
        }
        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        int p1 = dfs(matrix, i + 1, j, matrix[i][j], dp, n, m);
        int p2 = dfs(matrix, i - 1, j, matrix[i][j], dp, n, m);
        int p3 = dfs(matrix, i, j + 1, matrix[i][j], dp, n, m);
        int p4 = dfs(matrix, i, j - 1, matrix[i][j], dp, n, m);
        int p = Math.max(Math.max(p1, p2), Math.max(p3, p4)) + 1;
        dp[i][j] = p;
        return p;
    }

    public int solve3(int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int max = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!map.containsKey(i + "_" + j)) {
                    max = Math.max(max, dfs3(matrix, i, j, -1, map, n, m));
                }
            }
        }
        return max;
    }

    private int dfs3(int[][] matrix, int i, int j, int num, HashMap<String, Integer> map, int n, int m) {
        if (i < 0 || i >= n || j < 0 || j >= m || matrix[i][j] <= num) {
            return 0;
        }
        String key = i + "_" + j;
        if (map.containsKey(key)) {
            return map.get(key);
        }

        int p1 = dfs3(matrix, i + 1, j, matrix[i][j], map, n, m);
        int p2 = dfs3(matrix, i - 1, j, matrix[i][j], map, n, m);
        int p3 = dfs3(matrix, i, j + 1, matrix[i][j], map, n, m);
        int p4 = dfs3(matrix, i, j - 1, matrix[i][j], map, n, m);
        int val = Math.max(Math.max(p1, p2), Math.max(p3, p4)) + 1;
        map.put(key, val);
        return val;
    }

    public int solve2(int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int max = 0;
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!set.contains(i + "_" + j)) {
                    max = Math.max(max, dfs2(matrix, i, j, -1, set, n, m));
                }
            }
        }
        return max;
    }

    private int dfs2(int[][] matrix, int i, int j, int num, HashSet<String> set, int n, int m) {
        if (i < 0 || i >= n || j < 0 || j >= m || matrix[i][j] <= num) {
            return 0;
        }
        set.add(i + "_" + j);
        int p1 = dfs2(matrix, i + 1, j, matrix[i][j], set, n, m);
        int p2 = dfs2(matrix, i - 1, j, matrix[i][j], set, n, m);
        int p3 = dfs2(matrix, i, j + 1, matrix[i][j], set, n, m);
        int p4 = dfs2(matrix, i, j - 1, matrix[i][j], set, n, m);

        return Math.max(Math.max(p1, p2), Math.max(p3, p4)) + 1;
    }

    public int solve1(int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max = Math.max(max, dfs1(matrix, i, j, -1, n, m));
            }
        }
        return max;
    }

    private int dfs1(int[][] matrix, int i, int j, int num, int n, int m) {
        if (i < 0 || i >= n || j < 0 || j >= m || matrix[i][j] <= num) {
            return 0;
        }
        int p1 = dfs1(matrix, i + 1, j, matrix[i][j], n, m);
        int p2 = dfs1(matrix, i - 1, j, matrix[i][j], n, m);
        int p3 = dfs1(matrix, i, j + 1, matrix[i][j], n, m);
        int p4 = dfs1(matrix, i, j - 1, matrix[i][j], n, m);

        return Math.max(Math.max(p1, p2), Math.max(p3, p4)) + 1;
    }
}

发表于 2022-05-08 23:39:48 回复(0)

Java

GIOPPL

官方题解太难懂了,还是我的好懂

import java.util.*;

public class Solution {
public int solve(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
fun(matrix, i, j,Integer.MIN_VALUE);
}
}
return re;
}
//临时路径长度
int count = 0;
//结果
int re = 1;

private void fun(int[][] matrix, int i, int j, int v) {
//回溯的终止条件
if (i < 0 || i > matrix.length - 1 || j < 0 || j > matrix[i].length - 1 || v >= matrix[i][j]) {
re = Math.max(count, re);
return;
}
//以下是四个方向
if (i - 1 >= 0) {
count++;
fun(matrix, i - 1, j, matrix[i][j]);
count--;
}
if (i + 1 < matrix.length) {
count++;
fun(matrix, i + 1, j, matrix[i][j]);
count--;
}
if (j - 1 >= 0) {
count++;
fun(matrix, i, j - 1, matrix[i][j]);
count--;
}
if (j + 1 < matrix[i].length) {
count++;
fun(matrix, i, j + 1, matrix[i][j]);
count--;
}
}
}

发表于 2022-04-22 16:49:41 回复(0)

Java

我是小韩

暴力算法： DFS + 回溯

主要思路：以每一个点为起点进行遍历，判断是否可以上下左右移动，当不能进行移动时，表示此次遍历结束，判断长度。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    private static int result = 0;
    public int solve (int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                LinkedList<Integer> path = new LinkedList<>();
                path.add(matrix[i][j]);
                dfs(i,j,matrix, path);
            }
        }
        return result;
    }

    public void dfs(int x, int y, int[][] matrix, LinkedList<Integer> path) {
        // 左
        if (y > 0 && matrix[x][y - 1] > matrix[x][y]) {
            path.add(matrix[x][y]);
            dfs(x, y - 1, matrix, path);
            path.removeLast();
        }
        // 右
        if (y < matrix[0].length - 1 && matrix[x][y + 1] > matrix[x][y]) {
            path.add(matrix[x][y]);
            dfs(x, y + 1, matrix, path);
            path.removeLast();
        }
        // 上
        if (x > 0 && matrix[x - 1][y] > matrix[x][y]) {
            path.add(matrix[x][y]);
            dfs(x - 1, y, matrix, path);
            path.removeLast();
        }
        // 下
        if (x < matrix.length - 1 && matrix[x + 1][y] > matrix[x][y]) {
            path.add(matrix[x][y]);
            dfs(x + 1, y, matrix, path);
            path.removeLast();
        }
        // 结束标志
        if (result < path.size()) {
            result = path.size();
        }
        return;
    }
}

发表于 2022-04-10 00:40:20 回复(0)

Java

MChen-67

// 递归+记忆法+剪枝
public class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows, columns;

    public int solve(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        rows = matrix.length;
        columns = matrix[0].length;
        int[][] memo = new int[rows][columns];
        int ans = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                ans = Math.max(ans, dfs(matrix, i, j, memo));
            }
        }
        return ans;
    }

    public int dfs(int[][] matrix, int row, int column, int[][] memo) {
        if (memo[row][column] != 0) {
            return memo[row][column];
        }
        ++memo[row][column];
        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]) {
                memo[row][column] = Math.max(memo[row][column], dfs(matrix, newRow, newColumn, memo) + 1);
            }
        }
        return memo[row][column];
    }
}

发表于 2022-03-22 20:47:00 回复(0)

Java

***

1每个数组元素使用dfs算法遍历上下左右每种情况

2再从结果中选取最大值作为结果

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    
   Integer max=Integer.MIN_VALUE;
    public int solve (int[][] matrix) {
        // write code here
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                dfs(matrix,i,j,1);

            }
        }
        return max;
    }
    
    public void dfs(int[][] matrix,int x,int y,int data){
        if(y-1>=0&&matrix[x][y-1]>matrix[x][y]){
          
            dfs(matrix,x,y-1,data+1);
        }   
         if(y+1<matrix.length&&matrix[x][y+1]>matrix[x][y]){
            dfs(matrix,x,y+1,data+1);
        }  
        if(x-1>=0&&matrix[x-1][y]>matrix[x][y]){
            dfs(matrix,x-1,y,data+1);
        }
         if(x+1<matrix[0].length&&matrix[x+1][y]>matrix[x][y]){
            dfs(matrix,x+1,y,data+1);
        }
        
        max=Math.max(data,max);
        return;      
    }
    
    
}

发表于 2022-03-09 13:50:01 回复(0)

提交观点

问题信息

动态规划图 dfs

难度：

29条回答 757收藏 5199浏览

通过挑战的用户

查看代码

牛客89427...

2022-09-16 19:04:17
希望奇迹发生的...

2022-09-16 14:12:25
xxdev

2022-09-16 13:57:28
就是要HAPPY

2022-09-16 11:28:55
牛客45609...

2022-09-16 10:12:05

矩阵最长递增路径

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题