看汽车图片的网站可以做壁纸,浙江软装公司,常见的搜索引擎,广西壮族自治区住房和城乡建设厅一、题目描述 二、解题思路
1、先求出以矩阵中的每个单元格为起点的最长递增路径
题目中说#xff0c;对于每个单元格#xff0c;你可以往上#xff0c;下#xff0c;左#xff0c;右四个方向移动。那么以一个单元格为起点的最长递增路径就是#xff1a;从该单元格往上…一、题目描述 二、解题思路
1、先求出以矩阵中的每个单元格为起点的最长递增路径
题目中说对于每个单元格你可以往上下左右四个方向移动。那么以一个单元格为起点的最长递增路径就是从该单元格往上下左右四个方向走的四条递增路径中的最大值即最长的一条递增路径。
2、在求出的所有最长递增路径中找最大值
因为题目是求矩阵中的最长递增路径所以要在求出的所有最长递增路径中找最大值。
3、使用“记忆化搜索”递归“备忘录” 来解决该题。
三、 代码
class Solution {int m, n;//遍历上、下、左、右四个方向所需的数组int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};int[][] memo; //备忘录public int longestIncreasingPath(int[][] matrix) {m matrix.length;n matrix[0].length;memo new int[m][n];//求所有的最长递增路径中的最大值int ret 0;for(int i 0; i m; i) {for(int j 0; j n; j) {ret Math.max(ret,dfs(i, j, matrix));}}return ret;}//递归函数//求出以矩阵中的每个单元格为起点的最长递增路径上下左右四个方向中的最大值public int dfs(int i, int j, int[][] matrix) {if(memo[i][j] ! 0) {return memo[i][j];}int ret 1;for(int k 0; k 4; k) {int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n matrix[x][y] matrix[i][j]) {ret Math.max(ret, dfs(x,y,matrix)1);}}memo[i][j] ret;return ret;}
}
