题目描述

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = [ [9,9,4], [6,6,8], [2,1,1]]

输出:4

解释:最长递增路径为[1, 2, 6, 9]。

示例 2:

输入: nums = [ [3,4,5], [3,2,6], [2,2,1]]

输出: 4

解释: 最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。

解题思路：开始时想暴力的遍历矩阵，对每一个值DFS。提交后发现超时，最坏情况达到了o(n4)...于是增加了一个dp数组，相当于给递归加了缓存，用空间换时间。

 int DFS(int x,int y,vector<vector<int>>& matrix,vector<vector<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.size()&&x+i>=0&&y+j<matrix[0].size()&&y+j>=0)

             {

                 if(matrix[x][y]<matrix[x+i][y+j])

                 {

                     int k=DFS(x+i,y+j,matrix,dp)+1;

                     maxNum=max(maxNum,k);

                 }

             }

         }

     dp[x][y]=maxNum;

     return maxNum;

 }

 int longestIncreasingPath(vector<vector<int>>& matrix) {

     int Max=0;

     if(matrix.empty())

         return 0;

     vector<vector<int>> dp(matrix.size(),vector<int> (matrix[0].size()));

     for(int i=0;i<matrix.size();++i)

         for(int j=0;j<matrix[0].size();++j)

         {

             Max=max(DFS(i,j,matrix,dp),Max);

         }

     return Max;

 }