(C++) DFS solution with DP optimized~ 76ms but beat 97.6% ----what???


  • 2
    • dp[r][c] cache the LIS length started from matrix[r][c], since we will
      search all matrix[[r][c]'s LIS, we dont have to worry about when matrix[[r][c] is
      in the middle of an LIS.
    • for every matrix[[r][c], we search in 4directions to get its max LIS length, if what we search is already in cache, we use it.
    • NOTE that since we search for INCREASING, so we wont vist an position twice, such that we dont need an map to record the position that we have visted in DFS.

    code:

    class Solution {
    public:
        int longestIncreasingPath(vector<vector<int> >& matrix) {
            int m=0;
            row=matrix.size();
            if(row==0)
                return 0;
            col=matrix[0].size();
            dp.resize(row,vector<int>(col));
            for(int r=0;r<row;++r){
                for(int c=0;c<col;++c){
                    int inc=findIncreasing(r,c,matrix);
                    m=max(m,inc);
                }
            }
            return m;
        }
    private:
        int row,col;
        vector<vector<int> > dp;
        int findIncreasing(int r,int c,vector<vector<int> >& matrix){
            if(dp[r][c]>0)
                return dp[r][c];
            //cout<<"<"<<matrix[r][c]<<" ";
            int m=0;
            int now=matrix[r][c];
            //up
            if(r-1>=0 && matrix[r-1][c]>now){
                m=max(m,findIncreasing(r-1,c,matrix));
            }
            //down
            if(r+1<row && matrix[r+1][c]>now){
                m=max(m,findIncreasing(r+1,c,matrix));
            }
            //left
            if(c-1>=0 && matrix[r][c-1]>now){
                m=max(m,findIncreasing(r,c-1,matrix));
            }
            //right
            if(c+1<col && matrix[r][c+1]>now){
                m=max(m,findIncreasing(r,c+1,matrix));
            }
            dp[r][c]=m+1;
            return m+1;
        }
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.