目录
力扣329. 矩阵中的最长递增路径
解析代码1_爆搜递归（超时）
解析代码2_记忆化搜索
力扣329. 矩阵中的最长递增路径
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
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
}
};解析代码1_爆搜递归（超时）
- 递归含义：给 dfs 一个下标 [i, j] ，返回从这个位置开始的最长递增路径的长度。
- 函数体：上下左右四个方向看一看，哪里能过去就过去，统计四个方向上的最大长度。
- 递归出口：因为是先判断再进⼊递归，因此没有出口。
class Solution {
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int m = 0, n = 0;
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size(), n = matrix[0].size();
int ret = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
ret = max(ret, dfs(i, j, matrix));
}
}
return ret + 1; // 加上自己
}
int dfs(int sr, int sc, vector<vector<int>>& matrix)
{
int ret = 0;
for(int i = 0; i < 4; ++i)
{
int x = sr + dx[i], y = sc + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[sr][sc])
{
ret = max(ret, dfs(x, y, matrix) + 1);
}
}
return ret;
}
};
解析代码2_记忆化搜索
记忆化搜索解法：
- 加上一个备忘录。
- 每次进入递归的时候，去备忘录里面看看。
- 每次返回的时候，将结果加入到备忘录里面。
class Solution {
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int m = 0, n = 0;
int memo[201][201];
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size(), n = matrix[0].size();
int ret = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
ret = max(ret, dfs(i, j, matrix));
}
}
return ret + 1; // 加上自己
}
int dfs(int sr, int sc, vector<vector<int>>& matrix)
{
if(memo[sr][sc] != 0)
return memo[sr][sc];
int ret = 0;
for(int i = 0; i < 4; ++i)
{
int x = sr + dx[i], y = sc + dy[i];
if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[sr][sc])
{
ret = max(ret, dfs(x, y, matrix) + 1);
}
}
memo[sr][sc] = ret;
return ret;
}
};
