leetcode 329 Longest Increasing Path in a Matrix解题报告

首先很开心，在没有看任何解答的情况下解出了这道题！

方法一：

从每一个点出发，简单的DFS，单纯用mem来记录访问过的位置，当mem[i][j]=1时代表访问过数组，则以后不再访问。结果是超时了。

int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty())return 0;
        int ans=0;
        vector<vector<int>>mem(matrix.size());
        for(int i=0;i<matrix.size();i++){
            mem[i].resize(matrix[0].size(),0);
        }
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++){
                ans=max(ans,dfs(i,j,matrix,mem));
                //cout<<dfs(i,j,matrix,mem)<<endl;
            }
        return ans+1;
    }
    int dfs(int i,int j,vector<vector<int>>& matrix,vector<vector<int>> mem){
        if(mem[i][j]==1)return 0;
        mem[i][j]=1;
        vector<pair<int,int>>v{
         
  {0,1},{0,-1},{-1,0},{1,0}};
        int a=0;
        for(auto p:v){
            int x=i+p.first;
            int y=j+p.second;
            int num=0;
            if(x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size()){
                if(matrix[i][j]<matrix[x][y]) num=1+dfs(x,y,matrix,mem);
            }
            //cout<<num<<endl;
            a=max(a,num);
        }
        return a;
    }

方法二：

其实是基于方法一，只不过增加了mem的功能，用于记录访问过的位置的最长路径。将mem初始设为-1。

int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty())return 0;
        int ans=0;
        vector<vector<int>>mem(matrix.size());
        for(int i=0;i<matrix.size();i++){
            mem[i].resize(matrix[0].size(),-1);
        }
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++){
                ans=max(ans,dfs(i,j,matrix,mem));
            }
        return ans+1;
    }
    int dfs(int i,int j,vector<vector<int>>& matrix,vector<vector<int>> &mem){
        if(mem[i][j]!=-1)return mem[i][j];
        mem[i][j]=0;
        vector<pair<int,int>>v{
         
  {0,1},{0,-1},{-1,0},{1,0}};
        int a=0;
        for(auto p:v){
            int x=i+p.first;
            int y=j+p.second;
            int num=0;
            if(x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size()){
                if(matrix[i][j]<matrix[x][y]) num=1+dfs(x,y,matrix,mem);
            }
            //cout<<num<<endl;
            mem[i][j]=max(mem[i][j],num);
        }
        return mem[i][j];}

方法三：

改变了一下dfs的写法，本以为会小小提升一下速度，但是似乎没什么效果。

int longestIncreasingPath(vector<vector<int>>& matrix) {
    if(matrix.empty())return 0;
    int ans=0;
    vector<vector<int>>mem(matrix.size());
    for(int i=0;i<matrix.size();i++){
        mem[i].resize(matrix[0].size(),-1);
    }
    for(int i=0;i<matrix.size();i++)
        for(int j=0;j<matrix[0].size();j++){
            ans=max(ans,dfs(i,j,INT_MIN,matrix,mem));
        }
        return ans;
    }
    int dfs(int i,int j,int pre,vector<vector<int>>& matrix,vector<vector<int>> &mem){
        if(i>=matrix.size() || i<0 || j>=matrix[0].size() || j<0 || matrix[i][j]<=pre) return 0;
        if(mem[i][j]!=-1)return mem[i][j];
        vector<pair<int,int>>v{
         
  {0,1},{0,-1},{-1,0},{1,0}};
        int a=0;
        for(auto p:v){
            int x=i+p.first;
            int y=j+p.second;
            mem[i][j]=max(mem[i][j],1+dfs(x,y,matrix[i][j],matrix,mem));           
        }
        return mem[i][j];
    }