# Very concise solution also with nice performance in C, well-explained

• The first sight of this problem, it's not a DFS problem but rather it's more like a DP or Memoization problem though there are some traversing to search. Okay, just save the crap, hit the road. Memoization is going to be an easy way to go:

• use a 2-dimension array to store the states for each cell of the matrix;
• traverse starting from each cell to complete the states - the max length end in this cell;
• to avoid trying each direction using barehand-writing code, I choose to use an array to do that

Directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

which can be replaced with more direct method to improve the performance but it will be ugly comparably.

Bang! End of Story!

• space cost O (n*m) the matrix used to store the states;
• time cost O(n*m) since we are only required to fill all the states of the matrix of maxes;

Readability can not always be hand in hand with performance, try to balance them.

``````const int Directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool inRange(int r, int c, int rSize, int cSize)
{
return r>=0 && r<rSize && c>=0 && c<cSize;
}

int traverse(int r, int c, int rSize, int cSize, int** matrix, int** maxes)
{
if(!inRange(r, c, rSize, cSize)) return 0;
if(maxes[r][c] != -1) return maxes[r][c];
int cur = matrix[r][c];
int max = 1; //as long as it's valid, it will be at least 1;
int t = 0;
for(int i = 0; i < 4; i++) //check the cells around;
{
int r0 = r+Directions[i][0];
int c0 = c+Directions[i][1];
if(inRange(r0, c0, rSize, cSize) && cur > matrix[r0][c0])
{
t = traverse(r0, c0, rSize, cSize, matrix, maxes)+1;
if(t > max)
max = t;
}
}
return maxes[r][c] = max;//update the current cell;
}

int longestIncreasingPath(int** matrix, int rSize, int cSize)
{
int **maxes = (int**)malloc(sizeof(int*)*rSize);
for(int i = 0; i < rSize; i++) //initialize the maxes states matrix;
{
maxes[i] = (int*)malloc(sizeof(int)*cSize);
for(int j = 0; j < cSize; j++)
maxes[i][j] = -1;
}
int max = 0;
for(int r = 0; r < rSize; r++) //try to start the traversal from each cell;
{
for(int c = 0; c < cSize; c++)
{
int t = traverse(r, c, rSize, cSize, matrix, maxes);
if(t > max)
max = t;
}
}
return max;
}``````

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