Longest Increasing Path in a Matrix
给一个2d数组, 找出其中最长的递增路径. 用dp作为一个memo. 然后用longest去记录路径的最长值. 因为题目不要求返回路径, 所以直接返回值就可以.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class Solution { public int longestIncreasingPath(int[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int n = matrix.length; int m = matrix[0].length; int[][]dp = new int[n][m]; int longest = 1; for(int i = 0 ; i < n; i++) { for(int j = 0; j < m; j++) { longest = Math.max(longest, dfs(matrix,i,j,dp)); } } return longest; } public int dfs(int[][]matrix, int i , int j, int[][] dp) { if(dp[i][j] > 0) return dp[i][j]; int longest = 1; int cur = matrix[i][j]; if(i-1>=0 && matrix[i-1][j] > cur) //up longest = Math.max(longest, dfs(matrix, i-1,j,dp)+1); if(i+1 <=matrix.length-1 && matrix[i+1][j] > cur) //down longest = Math.max(longest, dfs(matrix, i+1,j,dp)+1); if(j-1>=0 && matrix[i][j-1] > cur) //left longest = Math.max(longest, dfs(matrix, i,j-1,dp)+1); if(j+1 <=matrix[0].length-1 && matrix[i][j+1] > cur) // right longest = Math.max(longest, dfs(matrix, i,j+1,dp)+1); dp[i][j] = longest; //set memo return dp[i][j]; } } |