329. Longest Increasing Path in a Matrix

My intituition is topology sort. I tried typical DFS solution for this problem as following, i.e. having a visited table to record if a node is visited. However, I got TLE.

1:  class Solution {  
2:  private:  
3:    int rows;  
4:    int cols;  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      vector<vector<bool>> path(rows, vector<bool>(cols, false));  
11:      int maxLen = 0;  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, path, i, j));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, vector<vector<bool>> &path, int i, int j) {  
20:      path[i][j] = true;  
21:      int len = 1;  
22:      if (i > 0 && !path[i-1][j] && matrix[i][j] < matrix[i-1][j]) len = max(len, 1+dfs(matrix, path, i-1, j));  
23:      if (j > 0 && !path[i][j-1] && matrix[i][j] < matrix[i][j-1]) len = max(len, 1+dfs(matrix, path, i, j-1));  
24:      if (i+1<rows && !path[i+1][j] && matrix[i][j] < matrix[i+1][j]) len = max(len, 1+dfs(matrix, path, i+1, j));  
25:      if (j+1<cols && !path[i][j+1] && matrix[i][j] < matrix[i][j+1]) len = max(len, 1+dfs(matrix, path, i, j+1));  
26:      path[i][j] = false;  
27:      return len;  
28:    }  
29:  };  

After revisiting my algorithm, I realized that if we can have the visited[i][j] to record the maximum length so far, I don’t have to go deep and it saves a lot of dfs time.

1:  class Solution {  
2:  private:  
3:    int rows;  
4:    int cols;  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      vector<vector<int>> pathLength(rows, vector<int>(cols, false));  
11:      int maxLen = 0;  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, pathLength, i, j));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, vector<vector<int>> &pathLength, int i, int j) {  
20:      if (pathLength[i][j] != 0) return pathLength[i][j];  
21:      int len = 1;  
22:      if (i > 0 && matrix[i][j] < matrix[i-1][j]) len = max(len, 1+dfs(matrix, pathLength, i-1, j));  
23:      if (j > 0 && matrix[i][j] < matrix[i][j-1]) len = max(len, 1+dfs(matrix, pathLength, i, j-1));  
24:      if (i+1<rows && matrix[i][j] < matrix[i+1][j]) len = max(len, 1+dfs(matrix, pathLength, i+1, j));  
25:      if (j+1<cols && matrix[i][j] < matrix[i][j+1]) len = max(len, 1+dfs(matrix, pathLength, i, j+1));  
26:      pathLength[i][j] = len;  
27:      return pathLength[i][j];  
28:    }  
29:  };  

When I revisited this problem, I made mistake in line 25. Instead of dfs, I had "dp[i][j] = max(dp[i][j], dp[ii][jj]+1)" because this seems to be sufficient for the example given by the problem. However, for case like [[3,4,5], [3,2,6], [2,2,1]] it is completely wrong.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      int maxLen = 0;  
11:      vector<vector<int>> dp(rows, vector<int>(cols, 1));  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, i, j, dp));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, int i, int j, vector<vector<int>> &dp) {  
20:      if (dp[i][j] != 1) return dp[i][j];  
21:      for (int d = 0; d < dir.size(); d++) {  
22:        int ii = i + dir[d].first;  
23:        int jj = j + dir[d].second;  
24:        if (ii < 0 || ii == rows || jj < 0 || jj == cols || matrix[i][j] >= matrix[ii][jj]) continue;  
25:        dp[i][j] = max(dp[i][j], dfs(matrix, ii, jj, dp) + 1);  
26:      }  
27:      return dp[i][j];  
28:    }  
29:  };