# Quite simple recursive yet accepted as best in cpp

• Memorization and DFS combination, hack it and accelerate it meantime!

``````class Solution {
private:
int rowSize, colSize;
int traverse(const vector<vector<int>>& matrix, vector<vector<int>>& max_lengths, int r, int c)
{
if(max_lengths[r][c]) return max_lengths[r][c];
int longest = 1;
if(r-1>-1 && matrix[r][c]>matrix[r-1][c]) longest = max(longest, traverse(matrix, max_lengths, r-1, c)+1);
if(c-1>-1 && matrix[r][c]>matrix[r][c-1]) longest = max(longest, traverse(matrix, max_lengths, r, c-1)+1);
if(r+1<rowSize && matrix[r][c]>matrix[r+1][c]) longest = max(longest, traverse(matrix, max_lengths, r+1, c)+1);
if(c+1<colSize && matrix[r][c]>matrix[r][c+1]) longest = max(longest, traverse(matrix, max_lengths, r, c+1)+1);
return max_lengths[r][c]=longest;
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
rowSize = matrix.size();
if(!rowSize) return 0;
colSize = matrix[0].size();
int longest = 0;
vector<vector<int>> max_lengths(rowSize, vector<int>(colSize, 0));
for(int r = 0; r < rowSize; r++)
for(int c = 0; c < colSize; c++)
longest = max(longest, traverse(matrix, max_lengths, r, c));
return longest;
}
};``````

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