# C++ Solution using dfs + memorization should be easy to understand

• ``````class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int ans = 0;
if(!matrix.size())
return ans;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
init(dp);
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
if(!dp[i][j]){
dfs(i, j, dp, matrix, ans, true);
}
}
}
init(dp);
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
if(!dp[i][j]){
dfs(i, j, dp, matrix, ans, false);
}
}
}

return ans;
}
private:
void dfs(int r, int c, vector<vector<int>> &dp, vector<vector<int>>& matrix, int &ans, bool isdec){
int n = dp.size(), m = dp[0].size();
for(int i = 0; i < 4; ++ i){
int nr = r + dir[i][0], nc = c + dir[i][1];
if(nr >= 0 && nr < n && nc >= 0 && nc < m ){
if(isdec){
if(matrix[r][c] > matrix[nr][nc]){
if(!dp[nr][nc]){
dfs(nr, nc, dp, matrix, ans, isdec);
}
dp[r][c] = max(dp[r][c], dp[nr][nc]);
}
}else{
if(matrix[r][c] < matrix[nr][nc]){
if(!dp[nr][nc]){
dfs(nr, nc, dp, matrix, ans, isdec);
}
dp[r][c] = max(dp[r][c], dp[nr][nc]);
}
}
}
}
++ dp[r][c];
ans = max(dp[r][c], ans);
}

void init(vector<vector<int>> &dp){
for(int i = 0; i < dp.size(); ++ i){
for(int j = 0; j < dp[0].size(); ++ j){
dp[i][j] = 0;
}
}
}
private:
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
};``````

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