难度：困难
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
如对本文有疑问， 点击进行留言回复！！
Python3以GitHub为例来实现模拟登录和爬取的实例讲解
网友评论