1. 题目链接：329. 矩阵中的最长递增路径
2. 题目描述：
给定一个
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提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
算法（记忆化搜索）：
算法思路：
-
递归含义：给
dfs一个使命，给他一个下标[i,j]，返回从这个位置开始的最长递增路径的长度 -
函数体：上下左右四个方向看一看，哪里能过去就过去，统计四个方向上的最大长度
-
递归出口：因为我们是先判断再进入递归，因此没有出口
-
用一个备忘录
-
每次进入递归的时候，去备忘录里面看看
-
每次返回的时候，将结果加入到备忘录里面
算法流程：
- 初始化变量
m和n，分别表示矩阵的行数和列数。 - 定义两个数组dx和
dy，分别表示四个方向的横坐标变化和纵坐标变化。 - 定义一个二维数组memo，用于存储已经计算过的最长递增路径长度。
- 遍历矩阵的每一行和每一列，对于每个位置
(i, j)，调用dfs函数来计算从该位置开始的最长递增路径长度。 dfs函数的作用是从当前位置(i, j)开始，向四个方向进行搜索，找到下一个值大于当前值的位置，然后递归地计算从该位置开始的最长递增路径长度。- 如果已经计算过某个位置的最长递增路径长度，则直接返回该值，避免重复计算。
- 在
dfs函数中，使用一个变量ret来记录当前位置的最长递增路径长度，初始值为1。 - 遍历四个方向，对于每个方向，计算下一个位置的坐标
(x, y)，如果下一个位置在矩阵范围内且值大于当前位置的值，则递归地计算从该位置开始的最长递增路径长度，并更新ret的值。 - 将当前位置的最长递增路径长度存入
memo数组，以便后续使用。 - 返回当前位置的最长递增路径长度。
- 在
longestIncreasingPath函数中，遍历矩阵的每一行和每一列，对于每个位置(i, j)，调用dfs函数来计算从该位置开始的最长递增路径长度，并更新ret的值。 - 最后，返回
ret作为结果，即矩阵中的最长递增路径长度。
C++算法代码：
class Solution {
int m, n; // 定义两个变量m和n，分别表示矩阵的行数和列数
int dx[4] = {0, 0, 1, -1}; // 定义一个数组dx，表示四个方向的横坐标变化
int dy[4] = {1, -1, 0, 0}; // 定义一个数组dy，表示四个方向的纵坐标变化
int memo[201][201]; // 定义一个二维数组memo，用于存储已经计算过的最长递增路径长度
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int ret = 0; // 初始化最长递增路径长度为0
m = matrix.size(), n = matrix[0].size(); // 获取矩阵的行数和列数
for (int i = 0; i < m; i++) { // 遍历矩阵的每一行
for (int j = 0; j < n; j++) { // 遍历矩阵的每一列
ret = max(ret, dfs(matrix, i, j)); // 更新最长递增路径长度
}
}
return ret; // 返回最长递增路径长度
}
int dfs(vector<vector<int>>& matrix, int i, int j) {
if (memo[i][j] != 0) return memo[i][j]; // 如果已经计算过该位置的最长递增路径长度，则直接返回
int ret = 1; // 初始化当前位置的最长递增路径长度为1
for (int k = 0; k < 4; k++) { // 遍历四个方向
int x = i + dx[k], y = j + dy[k]; // 计算下一个位置的坐标
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
// 如果下一个位置在矩阵范围内且值大于当前位置的值，则递归计算下一个位置的最长递增路径长度
ret = max(ret, dfs(matrix, x, y) + 1);
}
}
memo[i][j] = ret; // 将当前位置的最长递增路径长度存入memo数组
return ret; // 返回当前位置的最长递增路径长度
}
};
