[算法题解详细]DFS解力扣329矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例1

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出：4

解释：最长递增路径为 [1, 2, 6, 9]

示例2

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]

输出：4

解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例3

输入：matrix = [[1]]

输出：1

提示

1. m == matrix.length

2. n == matrix[i].length

3. 1 <= m, n <= 200

4. 0 <= matrix[i][j] <= 2^31 - 1

思路

---

刚看到这题的时候我以为这题和岛屿最大面积这题差不多，但是提交了几次代码后发现这两题有一个很不同的点，这个点就在于，

最大面积那题遍历整个矩阵，如果是1则加入面积，矩阵给出的1是固定的！

就是我们只需要遍历得到最多1在一起的个数就能得到，但是这一题不同，这一题有一个很大的问题就是我们遍历每一个点，进入dfs后进行上下左右的搜索，可能会同时有多条路径的存在！

如上图，多条路径的存在就会让这个问题复杂，我们只需要取最长的那条路径，并且因为这一题中我们不能标记已访问的点，所以会造成很多的重复计算，所以我们要使用一个备忘录数组来记录每个点以自身为起点的最长递增路径的大小，下面我们看代码

代码

---

首先是主函数中我们照样是遍历整个矩阵，但在遍历之前我们要先初始化备忘录，用于记录

class Solution {

public:

int m, n;

int dx[4] = {1 , -1 , 0 , 0};

int dy[4] = {0 , 0 , 1 , -1};

int longestIncreasingPath(vector<vector>& matrix) {

int ans = 0;

m = matrix.size();

n = matrix[0].size();

auto record = vector<vector>(m, vector(n , 0));

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

ans = max(ans, dfs(matrix, i, j, record));

}

}

return ans;

}

};

dx，dy两个数组是用来搜索上下左右四个方向的方向数组，这里我们还要注意dfs函数的类型为int，因为这里我们是用函数的返回值来得到最长递增路径的数值的

还有要注意auto这个关键字，这是c++11标准中的，它可以声明变量时根据初始化表达式自动推断该变量的类型，因此这里我直接让它推导record数组的类型，就不用自己判断了，十分方便

进入dfs函数，首先我们要判断这个点是不是已经计算过，因为备忘录record被初始化全为0，所以如果当前点值不为0的话那么这个点已经被计算过了，所以我们直接返回这个点的值

int dfs(vector<vector>& matrix, int x, int y, vector<vector>& record) {

if(record[x][y] != 0) {

return record[x][y];

}

}

这个直接返回record[x][xy]我们可以举一个例子来理解，

比方说我们遍历完示例1的第一排第二列的9，再往后一位遍历8的时候，我们从8向左搜索点就会搜索到点，这个时候record[0][1]是9所在位置备忘录的值，那么如果9已经被我们计算过了的话，我们可以直接返回record[0][1]的值供其他点进行计算

相反，如果当前点值为0的话，就说明这点还没有被计算过，因此我们给这个点+1，因为要求递增路径，每个点的值其实应该为1，因为一个数也是路径，只是路径长度为1而已

int dfs(vector<vector>& matrix, int x, int y, vector<vector>& record) {

if(record[x][y] != 0) {

return record[x][y];

}

++record[x][y];

}

然后我们要计算以当前点为起点的最长递增路径长度为多少，即搜索当前点的上下左右四个方向

int dfs(vector<vector>& matrix, int x, int y, vector<vector>& record) {

if(record[x][y] != 0) {

return record[x][y];

}

++record[x][y];

for(int i = 0; i < 4; i++) {

int a = x + dx[i];

int b = y + dy[i];

}

}

然后这里要注意一个写法，就是计算当前点的最长递增路径

if(a >= 0 && a < m && b >= 0 && b < n && matrix[a][b] > matrix[x][y]) {

record[x][y] = max(record[x][y] , dfs(matrix, a, b, record) + 1);

}

最后

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Android工程师，想要提升技能，往往是自己摸索成长，自己不成体系的自学效果低效漫长且无助。

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Android开发知识点！不论你是刚入门Android开发的新手，还是希望在技术上不断提升的资深开发者，这些资料都将为你打开新的学习之门！

如果你觉得这些内容对你有帮助，需要这份全套学习资料的朋友可以戳我获取！！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
85)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Android开发知识点！不论你是刚入门Android开发的新手，还是希望在技术上不断提升的资深开发者，这些资料都将为你打开新的学习之门！

如果你觉得这些内容对你有帮助，需要这份全套学习资料的朋友可以戳我获取！！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！