欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

329. 矩阵中的最长递增路径 深度优先+记忆化递归

程序员文章站 2022-05-01 08:29:36
329. 矩阵中的最长递增路径难度:困难2020/7/26每日一题打卡题目描述解题思路今天的困难题感觉不是很难诶,虽然我看了答案,但是大概知道要对每个位置的数字进行深度优先搜索然后取最大值,看一眼答案就写出来自己的了为了避免重复递归,进行记忆化,用一个数组来保存暂时的结果,搜索的时候如果dp[i][j] != 0,说明这里已经被搜索过,直接返回就可以。如果没访问过,在四个方向进行深度优先搜索,细节就是每次搜索都要+1/* * 329. 矩阵中的最长递增路径 *...

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

难度:困难
2020/7/26每日一题打卡
题目描述
329. 矩阵中的最长递增路径 深度优先+记忆化递归

解题思路
今天的困难题感觉不是很难诶,虽然我看了答案,但是大概知道要对每个
位置的数字进行深度优先搜索然后取最大值,看一眼答案就写出来自己的了
为了避免重复递归,进行记忆化,用一个数组来保存暂时的结果,搜索的时候如果dp[i][j] != 0,说明这里已经被搜索过,直接返回就可以。
如果没访问过,在四个方向进行深度优先搜索,细节就是每次搜索都要+1

/*
		     * 329. 矩阵中的最长递增路径
		     * 2020/7/26
		     */
		    public int longestIncreasingPath(int[][] matrix) {
		    	if(matrix == null || matrix.length == 0) {
		    		return 0;
		    	}
		    	int m = matrix.length;
		    	int n = matrix[0].length;
		    	int[][] dp = new int[m][n];
		    	int max = 0;
		    	//对每个位置都要进行深度优先搜索
		    	for (int i = 0; i < m; i++) {
					for (int j = 0; j < n; j++) {
						max = Math.max(max, increasingPathHelper(matrix, dp, Integer.MIN_VALUE, i, j, m, n));
					}
				}
		    	return max;

		    }
		    //深度优先搜索
		    public int increasingPathHelper(int[][] matrix,int[][] dp,int cur,int i,int j,int m,int n) {
		    	
		    	//如果数组越界或者不大于当前元素,返回
		    	if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] <= cur) {
		    		return 0;
		    	}
		    	//记忆化。如果i,j位置已经访问过,直接返回结果
		    	if(dp[i][j] != 0) {
		    		return dp[i][j];
		    	}
		    	
		    	//四个方向去搜索,找最大的那个
		    	int up = increasingPathHelper(matrix, dp, matrix[i][j], i-1, j, m, n);
		    	int down = increasingPathHelper(matrix, dp, matrix[i][j], i+1, j, m, n);
		    	int left = increasingPathHelper(matrix, dp, matrix[i][j], i, j-1, m, n);
		    	int right = increasingPathHelper(matrix, dp, matrix[i][j], i, j+1, m, n);
		    	
		    	
		    	int temp =  Math.max(Math.max(up, down),Math.max(left, right));
		    	dp[i][j] = temp + 1;  //记忆
		    	return temp + 1;
		    	
				
			}

329. 矩阵中的最长递增路径 深度优先+记忆化递归

本文地址:https://blog.csdn.net/hh155715/article/details/107589670

相关标签: 力扣刷题笔记