题意

给定一个数字矩阵，找出一条路径使其经过的数字递增且最长。

思路

对于类迷宫题目，我们可以直接使用深度优先搜索与回溯法，把所有可能的路径求出，再找到其中最长的路径，只使用最朴素的思路，得出的代码如下。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int n,m,ans=-1;
    const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//方向数组
    bool isValid(int posX,int posY)
    {
        return posX>=0 && posY>=0 && posX<n && posY<m;//判断当前位置是否合法
    }
    int dfs(int posX,int posY,vector<vector<int> > &matrix)
    {
        int maxx=1;
        for(int i=0;i<4;i++)
        {
            if(!isValid(posX+dx[i],posY+dy[i])) continue; 
            if(matrix[posX+dx[i]][posY+dy[i]]>matrix[posX][posY])//若递增
                maxx=max(dfs(posX+dx[i],posY+dy[i],matrix)+1,maxx);//寻找最长路径
        }
        return maxx;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        n=matrix.size();
        m=matrix[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) ans=max(dfs(i,j,matrix),ans);//从每一处开始寻找
        return ans;
    }
};

复杂度分析

时间复杂度:$O(n^2{m}^2)O(n^2m^2)$，对于矩阵中每一个点都进行了搜索，每次搜索最坏为$O(nm)O(nm)$的。

空间复杂度:$O(nm)O(nm)$，存储矩阵所用。

改进

上面的代码虽然可以通过题目，但是没有达到复杂度要求，思考后我们可以发现对于每个点，以其为起点的最长路径在搜索中不改变，故我们可以使用记忆化搜索用空间换时间来降低时间复杂度，代码如下。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int n,m,ans=-1;
    int dp[1005][1005]={0};//记忆从i,j开始的最长路径
    const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//方向数组
    bool isValid(int posX,int posY)
    {
        return posX>=0 && posY>=0 && posX<n && posY<m;//判断当前位置是否合法
    }
    int dfs(int posX,int posY,vector<vector<int> > &matrix)
    {
        if(dp[posX][posY]) return dp[posX][posY];//如果已经求过该点路径
        int maxx=1;
        for(int i=0;i<4;i++)
        {
            if(!isValid(posX+dx[i],posY+dy[i])) continue; 
            if(matrix[posX+dx[i]][posY+dy[i]]>matrix[posX][posY])//若递增
                maxx=max(dfs(posX+dx[i],posY+dy[i],matrix)+1,maxx);//寻找最长路径
        }
        return dp[posX][posY]=maxx;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        n=matrix.size();
        m=matrix[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) ans=max(dfs(i,j,matrix),ans);//从每一处开始寻找
        return ans;
    }
};

复杂度分析

时间复杂度:$O(nm)O(nm)$，对于矩阵中每一个点都进行了搜索，但每次搜索平均所用时间为常数级别。

空间复杂度:$O(nm)O(nm)$，存储矩阵所用。