# Sharing my C++ soln; 76ms; beats 89.95%;

• Just a normal recursion embedded in a memoization

``````class Solution {
public:
int m,n;
bool isOk(int x, int y){
return x>=0 && x<m && y>=0 && y<n;
}
int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>> &dp){
if(isOk(x,y)){
if(dp[x][y]!=-1) return dp[x][y];
int curr = matrix[x][y], mx=0;
if(isOk(x-1, y) && curr < matrix[x-1][y]){
mx = max(mx, dfs(matrix, x-1, y, dp));
}
if(isOk(x, y-1) && curr < matrix[x][y-1]){
mx = max(mx, dfs(matrix, x, y-1, dp));
}
if(isOk(x+1, y) && curr < matrix[x+1][y]){
mx = max(mx, dfs(matrix, x+1, y, dp));
}
if(isOk(x, y+1) && curr < matrix[x][y+1]){
mx = max(mx, dfs(matrix, x, y+1, dp));
}
dp[x][y]=mx+1;
return mx+1;
}else{
return 0;
}
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int ret = 0;
m = matrix.size();
if(m==0) return 0;
n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, -1));
for(int x=0;x<m;x++){
for(int y=0;y<n;y++){
if(dp[x][y]==-1){
ret = max(ret, dfs(matrix, x, y, dp));
} else {
ret = max(ret, dp[x][y]);
}
}
}
return ret;
}
};``````

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