# 64ms C++ solution, DFS + DP

• Basic DFS may result in TLE (Time Limit Exceeded) because of duplicate calculation. Thus it seems reasonable to sacrifice space for time: use a map for positions where max increasing length (starting from this position) has been calculated.
See code below:

``````class Solution {
public:
int maxLength = INT_MIN;
vector<vector<int>> maxLengthMap;
int DFS_VISIT(vector<vector<int>>& matrix, int i, int j, int maxRowNum, int maxColumnNum) {
if (maxLengthMap[i][j] > 0) // If position (i,j) has already been calculated, no need for redundant work
return maxLengthMap[i][j];
int leftMaxLength = 0;
int rightMaxLength = 0;
int upMaxLength = 0;
int downMaxLength = 0;
if (j-1 <= maxColumnNum && j-1 >= 0 && matrix[i][j-1] > matrix[i][j]) { // Go left
leftMaxLength = DFS_VISIT(matrix, i, j-1, maxRowNum, maxColumnNum);
}
if (j+1 <= maxColumnNum && j+1 >= 0 && matrix[i][j+1] > matrix[i][j]) { // Go right
rightMaxLength = DFS_VISIT(matrix, i, j+1, maxRowNum, maxColumnNum);
}
if (i-1 <= maxRowNum && i-1 >= 0 && matrix[i-1][j] > matrix[i][j]) { // Go up
upMaxLength = DFS_VISIT(matrix, i-1, j, maxRowNum, maxColumnNum);
}
if (i+1 <= maxRowNum && i+1 >= 0 && matrix[i+1][j] > matrix[i][j]) { // Go down
downMaxLength = DFS_VISIT(matrix, i+1, j, maxRowNum, maxColumnNum);
}
// maxLength = max(maxLength,curLength);
maxLengthMap[i][j] = max(max(leftMaxLength, rightMaxLength), max(upMaxLength, downMaxLength)) + 1;
return maxLengthMap[i][j];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int n = matrix.size(); // #rows
if (n == 0)
return 0;
int m = matrix[0].size(); // #columns
if (m == 0) // Empty input
return 0;
vector<int> tempL(m,0);
for (int i=0;i<n;i++)
maxLengthMap.push_back(tempL);
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
int curLength = DFS_VISIT(matrix, i, j, n-1, m-1); // DFS current position (i,j)
maxLength = max(maxLength, curLength);
}
}
return maxLength;
}
};
``````

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