题意分析

• 给出一个二维矩阵，矩阵的每个位置有一个数字，我们需要任意选择一个起点，然后从这个起点出发，每次只能走比当前数字更大的位置，问我们最多可以走多少步。
• 每次走的位置只能是上下左右四个方向，同时不能越界。每个格子最多只能走一次。

思路分析

• 一个DFS的操作，我们发现，我们可以枚举某一个起点，然后进行递归操作，用一个递归函数表示从这个位置开始可以最多走多少步。然后由四个方向的位置进行转移过来。一旦发现在过程中不符合题目的条件，我们直接进行返回0即可。

解法一 暴力DFS

• 我们直接暴力枚举每个起点进行DFS，在过程中维护最大值即可。递归直接往四个方向进行即可，但是首先需要先判断四个方向的位置是否是可行的，也就是是否会出现越界的情况。

• 代码如下
  • 时间复杂度为$O(nm)O(nm)$,每次DFS可能会遍历整个矩阵，每个位置有四个方向，最坏的时间复杂度为$O(nm{4}^{nm})O(nm4^\{nm\})$
  • 我们每次需要进行递归，最坏的递归的情况是遍历nm层，空间复杂度为$O(nm)O(nm)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int dfs(vector<vector<int> > &mat,int x,int y,int pre){
        // 如果到达这个位置的时候的长度大于等于之前得到的所有的位置
        if(pre>=mat[x][y]){
            return 0;
        }
        int mx=0;
        // 记录这个位置开始往四个方向遍历得到的最长的长度，类似于记忆化搜索
        if(x+1<mat.size()){
            mx=max(mx,dfs(mat,x+1,y,mat[x][y]));
        }
        if(x-1>=0){
            mx=max(mx,dfs(mat,x-1,y,mat[x][y]));
        }
        if(y-1>=0){
            mx=max(mx,dfs(mat,x,y-1,mat[x][y]));
        }
        if(y+1<mat[0].size()){
            mx=max(mx,dfs(mat,x,y+1,mat[x][y]));
        }
        
        return mx+1;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        int n=matrix.size();
        // 特判矩阵为空的情况
        if(n==0){
            return 0;
        }
        int ans=0;
        int m=matrix[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 枚举每个起点的位置
                ans=max(ans,dfs(matrix,i,j,-1));
            }
        }
        
        return ans;
    }
};

解法二 记忆化搜索

• 我们发现，如果我们在某一个过程中遍历到了(x,y)这个位置的时候，我们可以利用递归计算出这个位置开始可以走多少步。那么如果我们下次计算新的起始点的时候再走到了这个位置的时候，我们没有必要继续执行递归的操作了，我们可以直接利用之前递归得到的结果拿来用就行了。但是这样的方法我们需要额外开空间存储所有的位置的状态，这就是典型的空间换时间的做法，如果到了某一个位置的时候已经计算过，我们直接用，这样就减少了遍历的必要。

• 代码如下

  • 每个位置只需要遍历一次，所以总的时间复杂度为$O(nm)O(nm)$
  • 需要存储每个位置为起始点的时候的状态，同时递归的层数为nm,空间复杂为$O(nm)O(nm)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int dfs(vector<vector<int> > &mat,vector<vector<int> > &dp,int x,int y,int pre){
        if(mat[x][y]<=pre){
            return 0;
        }
        int n=mat.size();
        int m=mat[0].size();
        // 进行记忆化搜索
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        int mx=0;
        // 分别向四个方向进行转移
        if(x+1<n){
            mx=max(mx,dfs(mat,dp,x+1,y,mat[x][y]));
        }
        if(x-1>=0){
            mx=max(mx,dfs(mat,dp,x-1,y,mat[x][y]));
        }
        if(y-1>=0){
            mx=max(mx,dfs(mat,dp,x,y-1,mat[x][y]));
        }
        if(y+1<m){
            mx=max(mx,dfs(mat,dp,x,y+1,mat[x][y]));
        }
        
        // 更新这个位置的状态
        dp[x][y]=mx+1;
        
        return mx+1;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        
        int n=matrix.size();
        // 特判为空的情况
        if(n==0){
            return 0;
        }
        int m=matrix[0].size();
        // 初始化操作
        vector<vector<int> > dp(n,vector<int> (m,-1));
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                ans=max(ans,dfs(matrix,dp,i,j,-1));
            }
        }
        
        return ans;
    }
};