DFS + memorization


  • 0
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            row = matrix.size();
            col = row? matrix[0].size() : 0;
            int res = 0;
            memo = vector<vector<int>>(row, vector<int>(col));
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < col; ++j)
                    res = max(res, maxPath(matrix, i, j));
            return res;
        }
        
    private:
        int row, col;
        vector<vector<int>> memo;
        
        // get matrix value with default INT_MIN if out of range
        int getVal(vector<vector<int>>& matrix, int i, int j) {
            return (i >= 0 && i < row && j >= 0 && j < col)? matrix[i][j] : INT_MIN;
        }
        // longest path length starting from cell (i, j)
        int maxPath(vector<vector<int>>& matrix, int i, int j) {
            if (getVal(matrix, i, j) == INT_MIN) return 0;
            if (memo[i][j]) return memo[i][j];
            
            if (getVal(matrix, i+1, j) > matrix[i][j]) memo[i][j] = max(memo[i][j], maxPath(matrix, i+1, j));
            if (getVal(matrix, i-1, j) > matrix[i][j]) memo[i][j] = max(memo[i][j], maxPath(matrix, i-1, j));
            if (getVal(matrix, i, j+1) > matrix[i][j]) memo[i][j] = max(memo[i][j], maxPath(matrix, i, j+1));                       
            if (getVal(matrix, i, j-1) > matrix[i][j]) memo[i][j] = max(memo[i][j], maxPath(matrix, i, j-1));
            
            return ++memo[i][j];
        }
    

Log in to reply
 

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