LeetCode 329. 矩阵中的最长递增路径（DFS+记忆化（DP的思想）、拓扑排序）_dfs 矩阵最长路径

2020年9月28日 周一 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

1. DFS+记忆化(DP的思想)

DFS是非常直观的方法。从一个单元格进行DFS，即可找到从该单元格开始的最长递增路径。对每个单元格分别进行DFS之后，即可得到矩阵中的最长递增路径的长度。

但是这样做时间复杂度过高，原因是存在大量的重复计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。 用矩阵 memo 作为缓存矩阵，将已经计算过的结果存储到缓存矩阵中，第二次遍历到就能直接使用，这也是DP的思想。

class Solution {
   
public:
    static constexpr int dir[4][2]={
   {
   -1,0},{
   1,0},{
   0,-1},{
   0,1}};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
   
        if(matrix.size()==0 || matrix[0].size()==0) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        // memo存放从坐标P(i,j)出发的最长递增路径，将已经计算过的结果保存下来，避免重复计算
        vector<vector<int>> memo(m,vector<int>(n,0));
        int maxLen = 0;
        for(int i=0;i<m;++i){
   
            for(int j=0;j<n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19