【DFS 或 BFS 或拓扑排序 - LeetCode】329. 矩阵中的最长递增路径

题目: 

329. 矩阵中的最长递增路径

题解

DFS 搜索 + 记忆化

算是一个比较标准的、可以直接用来当做模版。

class Solution {
public:static constexpr int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};int rows, cols;int dfs(vector<vector<int>>&matrix, int row, int col, vector<vector<int>>&dist){// 已经搜索过if(dist[row][col] != 0){return dist[row][col];}dist[row][col] ++;for(int i = 0; i < 4; i ++){int x = row + d[i][0];int y = col + d[i][1];if(x >= 0 && x < rows && y>= 0 && y < cols && matrix[x][y] > matrix[row][col]){// 记忆化搜索，并存储符合条件情况dist[row][col] = max(dist[row][col], dfs(matrix,x,y,dist)+1);}}return dist[row][col];}int longestIncreasingPath(vector<vector<int>>& matrix) {if(matrix.size() == 0 || matrix[0].size() == 0){return 0;}rows = matrix.size();cols = matrix[0].size();auto dist = vector<vector<int>>(rows, vector<int>(cols));int ans = 0;for(int i = 0; i < rows; i ++){for(int j = 0; j < cols; j ++){// 依次对每一个点进行dfsans = max(ans, dfs(matrix,i,j,dist)); }}return ans;}
};