矩阵最长递增路径

深搜+dp即可。

  private int[][] dirs=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    private int m,n;
    public int solve (int[][] matrix) {
        // write code here

        if(matrix.length==0||matrix[0].length==0) return 0;
        m=matrix.length;
        n=matrix[0].length;
        int res=0;
        int[][] dp=new int[m+1][n+1];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){

                res=Math.max(res,dfs(matrix,dp,i,j));

            }
        }

        return res;
    }
    public int dfs(int[][] matrix,int[][] dp,int i,int j){

        if(dp[i][j]!=0) return dp[i][j];
        dp[i][j]++;

        for (int k=0;k<4;k++){
            int nexti=i+dirs[k][0];
            int nextj=j+dirs[k][1];

            if(nexti>=0&&nexti<m&&nextj>=0&&nextj<n&&matrix[nexti][nextj]>matrix[i][j]){
                dp[i][j]=Math.max(dp[i][j],dfs(matrix,dp,nexti,nextj));
            }
        }
        return dp[i][j];
    }
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 17:10
点赞 评论 收藏
分享
昨天 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
正义执行官:人家能回你就不错了,自己不主动去问,等着天上掉馅饼,想啥呢哥们
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务