My DP solution with Explanation, Search nearby using DFS. O(MN), Easy to read


  • 10
    A

    The question is just a 2 dimensional version of LIS. We can use brute force, but it is too costful. By storing the longest number of increasing subsequence starting from the node (i,j) in a 2d array, we can effectively prune many redundant recursive computations (although it's a dfs).

    int longestpath(vector<vector<int>>& matrix, vector<vector<int>>& states, int i, int j, int m, int n) {
        if(states[i][j] > 0)
            return states[i][j];
        
        int maxd = 0;
        
        if(j>0 && matrix[i][j-1] < matrix[i][j]) {
            int left = longestpath(matrix, states, i, j-1, m, n);
            maxd = max(maxd, left); 
        }
        if(j<n-1 && matrix[i][j+1] < matrix[i][j]) {
            
            int right = longestpath(matrix, states, i, j+1, m, n);
            maxd = max(maxd, right);
        };
        if(i>0 && matrix[i-1][j] < matrix[i][j]) {
            int up = longestpath(matrix, states, i-1, j, m, n);
            maxd = max(maxd, up);
            
        };
        if(i<m-1 && matrix[i+1][j] < matrix[i][j]) {
            int down = longestpath(matrix, states, i+1, j, m, n);
            maxd = max(maxd, down);
        };
        
        states[i][j] = maxd + 1;
        return states[i][j];
        
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        
        
        int m = matrix.size(); 
        if (m == 0) return 0;
        int n = matrix[0].size();
        int res = 0;
        
        vector<vector<int>> states(m, vector<int>(n, 0));
        
        for(int i = 0; i < m; ++ i) {
            
            for(int j = 0; j < n; ++ j) {
             //each element
             
             res = max(res, longestpath(matrix, states, i, j, m, n));
    
            }
            
        }
        
        return res;        
        
    }

  • 3
    J

    Same idea as yours, nice work ;)

    class Solution {
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
    		int m = matrix.size();
    		if(!m)	return 0;
    		int n = matrix[0].size(), maxSum = 0;
    		vector<vector<int> > pathSum(m, vector<int>(n , 1));
    		for(int i = 0; i < m; ++i)
    			for(int j = 0; j < n; ++j)
    				if(pathSum[i][j] == 1)
    					maxSum = max(maxSum, dfs(matrix, pathSum, m, n, i, j));
    		return maxSum;
        }
    
    private:
    	int dfs(vector<vector<int>>& matrix, vector<vector<int> > &pathSum, int m, int n, int i, int j){
    		if(pathSum[i][j] > 1)	return pathSum[i][j];
    		int res = 1;
    		if(i - 1 >= 0 && matrix[i][j] < matrix[i - 1][j])	res = max(res, 1 + dfs(matrix, pathSum, m, n, i - 1, j));
    		if(j - 1 >= 0 && matrix[i][j] < matrix[i][j - 1])	res = max(res, 1 + dfs(matrix, pathSum, m, n, i, j - 1));
    		if(i + 1 < m && matrix[i][j] < matrix[i + 1][j])	res = max(res, 1 + dfs(matrix, pathSum, m, n, i + 1, j));
    		if(j + 1 < n && matrix[i][j] < matrix[i][j + 1])	res = max(res, 1 + dfs(matrix, pathSum, m, n, i, j + 1));
    		pathSum[i][j] = res;
    		return res;
    	}
    };
    

  • 0
    U
    This post is deleted!

  • 0
    C

    thanks for you solution. but what does pathSum[i][j]=1 mean?


  • 0
    J

    It means the path which starts in (i, j) hasn't been calculated, so you should calculate it. Otherwise it has already been calculated and the current maxSum must be greater than it, so there is no need to calculate it again.


  • 0
    W

    I doubt it's time O(MN)


  • 0
    M

    I don't think you need if (pathSum[i][j] == 1) in for loop, since pathSum only update the current node each time, it won't affect the value of followings. So pathSum[i][j] will always be 1 when you first visit it.


  • 0
    J

    What do you mean by "since pathSum only update the current node each time"? In fact, when enters one recursion, it will update all the nodes it traverses.


  • 0
    L

    I doubt it too


Log in to reply
 

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