admin管理员组

文章数量:1037775

记忆化搜索系列一＞矩阵中的最长递增路径

题目分析：

链接: 题目链接

记忆化搜索方法：

代码呈现：

代码语言：javascript代码运行次数：0运行复制
class Solution {

    int m,n;
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int[][] mome;

    public int longestIncreasingPath(int[][] matrix) {
        int ret = 0;
        m = matrix.length;
        n = matrix[0].length;
        mome = new int[m][n];

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                ret = Math.max(ret, dfs(matrix,i,j));

        return ret;   

    }

    private int dfs(int[][] matrix, int i, int j){
        if(mome[i][j] != 0)
            return mome[i][j];

        int ret = 1;//至少有一个最长递增路径

        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j + dy[k];
            
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = Math.max(ret, dfs(matrix,x,y)+1);//注意进去第一个位置满足条件也算递增路径
            }
        }

        mome[i][j] = ret;
        return mome[i][j];
    }

}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-11，如有侵权请联系 cloudcommunity@tencent 删除dfsintmatrixreturn搜索

记忆化搜索系列一＞矩阵中的最长递增路径

题目分析：

链接: 题目链接

记忆化搜索方法：

代码呈现：

代码语言：javascript代码运行次数：0运行复制
class Solution {

    int m,n;
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int[][] mome;

    public int longestIncreasingPath(int[][] matrix) {
        int ret = 0;
        m = matrix.length;
        n = matrix[0].length;
        mome = new int[m][n];

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                ret = Math.max(ret, dfs(matrix,i,j));

        return ret;   

    }

    private int dfs(int[][] matrix, int i, int j){
        if(mome[i][j] != 0)
            return mome[i][j];

        int ret = 1;//至少有一个最长递增路径

        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j + dy[k];
            
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = Math.max(ret, dfs(matrix,x,y)+1);//注意进去第一个位置满足条件也算递增路径
            }
        }

        mome[i][j] = ret;
        return mome[i][j];
    }

}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-11，如有侵权请联系 cloudcommunity@tencent 删除dfsintmatrixreturn搜索

本文标签： 记忆化搜索系列一＞矩阵中的最长递增路径

版权声明：本文标题：记忆化搜索系列一＞矩阵中的最长递增路径 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748340925a2287963.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。