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

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

难度：困难
2020/7/26每日一题打卡
题目描述

解题思路
今天的困难题感觉不是很难诶，虽然我看了答案，但是大概知道要对每个
位置的数字进行深度优先搜索然后取最大值，看一眼答案就写出来自己的了
为了避免重复递归，进行记忆化，用一个数组来保存暂时的结果，搜索的时候如果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;
		    	
				
			}

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