LeetCode329. 矩阵中的最长递增路径

 dfs,主函数中枚举起点,然后dfs函数中枚举四个方向进行移动,但是光dfs还不够,因为我们发现存在很多冗余,所以这是一道dfs+dp的问题,resulti表示以i,j为终点的最长递增路径的长度

class Solution {
    public int n,m;
    public int[][] dr = {{-1,0},{1,0},{0,-1},{0,1}};
    public int[][] result = new int[1000][1000];
    public boolean check(int x,int y,int nx,int ny,int[][] matrix) {
        return nx >= 0 && ny >= 0 && nx < n && ny < m && matrix[nx][ny] > matrix[x][y];
    }
    public int dfs(int x,int y,int[][] matrix) {
        int max = 0;
        if(result[x][y] != 1)
            return result[x][y];
        for(int i = 0;i < 4;i++) {
            int nx = x + dr[i][0];
            int ny = y + dr[i][1];
            if(check(x,y,nx,ny,matrix))
                result[x][y] = Math.max(result[x][y],dfs(nx,ny,matrix) + 1);
        }
        return result[x][y];
    }
    public int longestIncreasingPath(int[][] matrix) {
        n = matrix.length;
        if(n == 0)
            return 0;
        m = matrix[0].length;
        int ans = 0;
        for(int i = 0;i < 1000;i++) 
            for(int j = 0;j < 1000;j++) 
                result[i][j] = 1;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                ans = Math.max(ans,dfs(i,j,matrix));
            }
        }
        return ans;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Laoqi's Linux运维专列

python3–内置模块Ⅱ

4978
来自专栏从流域到海域

《笨办法学Python》 第41课手记

《笨办法学Python》 第41课手记 本节课的代码有168行,但是冗长不代表困难,只是print里面的游戏说明内容太多,整体来说是很容易的,你要锻炼自己的耐心...

3567
来自专栏开发与安全

从零开始学C++之虚继承和虚函数对C++对象内存模型造成的影响(类/对象的大小)

首先重新回顾一下关于类/对象大小的计算原则: 类大小计算遵循结构体对齐原则 第一个数据成员放在offset为0的位置 其它成员对齐至min(sizeof(me...

2280
来自专栏数据结构与算法

07:机器翻译

7:机器翻译 总时间限制: 1000ms 内存限制: 65536kB描述 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件...

4156
来自专栏java一日一条

8张图理解Java

HashCode被设计用来提高性能。equals()方法与hashCode()方法的区别在于:

781
来自专栏java思维导图

8张图理解Java,一图胜千言

一图胜千言,下面图解均来自Program Creek 网站。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。 1、字符串不变性 下面这张图展示了这段代码...

2473
来自专栏前端儿

队花的烦恼一

ACM队的队花C小+经常抱怨:“C语言中的格式输出中有十六、十、八进制输出,然而却没有二进制输出,哎,真遗憾!谁能帮我写一个程序实现输入一个十进制数n,输出它的...

812
来自专栏xingoo, 一个梦想做发明家的程序员

圆排列问题-回溯法

问题描述:     给定n个大小不等的圆 c1 c2 c3 c4 要将n个圆排进一个矩形框中,且要求底边相切。找出有最小长度的圆排列。     例如:当n=3,...

2589
来自专栏吴伟祥

关于“分类”的应用 原

三、SQL中区分类别的过滤条件:比如取分类2,那么就是 2=2 <![CDATA[ & ]]>type

872
来自专栏精讲JAVA

8 张图理解 Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

931

扫码关注云+社区

领取腾讯云代金券