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

1、题目

https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/submissions/

2、题解

第一步，对每一个值进行DFS。第二步，增加了一个dp数组，相当于给递归加了缓存，用空间换时间。

3、代码

class Solution {
       public int longestIncreasingPath(int[][] matrix) {

           int Max=0;

           if(matrix.length==0||matrix[0].length==0){
               return 0;
           }
           int rows = matrix.length;
           int columns = matrix[0].length;
           int[][] dp=new int[rows][columns];

           for(int i=0;i<rows;++i){
               for(int j=0;j<columns ;++j) {
                   Max=getMax(getDfs(i,j,matrix,dp),Max);
               }
           }

           return Max;

       }
       private int getDfs(int x,int y,int[][] matrix,int[][] dp){
           if(dp[x][y]!=0){
               return dp[x][y];
           }
           int maxNum=1;
           for(int i=-1;i<=1;++i)
               for(int j=-1;j<=1;++j) {
                   if((i+j==-1||i+j==1)&&x+i<matrix.length&&x+i>=0&&y+j<matrix[0].length&&y+j>=0) {
                       if(matrix[x][y]<matrix[x+i][y+j]) {
                           int k=getDfs(x+i,y+j,matrix,dp)+1;
                           maxNum=getMax(maxNum,k);
                       }
                   }
               }
           dp[x][y]=maxNum;
           return maxNum;
       }
       //得到最大整数值
       private int getMax(int... values){
           int maxValue = Integer.MIN_VALUE;
           for (int value:values){
               if(value>maxValue){
                   maxValue=value;
               }
           }
           return maxValue;
       }

   }

4、执行结果