【记忆化搜索】矩阵中的最长递增路径

文章目录

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.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

解题思路：暴搜 -> 记忆化搜索

如果抛开什么记忆化搜索的思想来看，这道题和前面遇到的递归问题都是异曲同工之妙，直接用暴搜就能解决，我们枚举以每个元素为起点的最长递增路径长度，然后求出其中的最大值即可！

并且 不需要使用 used 数组来进行重复路径判断，因为我们能递归的就是向大元素方向走，此时下一层是不可能返回来的，因为我们加了判断只有元素变大的方向才会去递归！

class Solution {
public:int longestIncreasingPath(vector<vector<int>>& matrix) {// 通过dfs函数获取以每个元素为起点的最长递增路径长度，然后求出其中的最大值即可int ret = 1;for(int i = 0; i < matrix.size(); ++i)for(int j = 0; j < matrix[i].size(); ++j)ret = max(ret, dfs(matrix, i, j));return ret;}int dfs(vector<vector<int>>& matrix, int i, int j){// 递归函数出口if(i < 0 || i == matrix.size() || j < 0 || j == matrix[i].size())return 0;// 递归上下左右方向求出其最长递增路径长度，然后加上当前元素的长度也就是1，求出最大的方向长度int ret = 1;if(i - 1 >= 0 && matrix[i][j] < matrix[i - 1][j])ret = max(ret, dfs(matrix, i - 1, j) + 1);if(j - 1 >= 0 && matrix[i][j] < matrix[i][j - 1])ret = max(ret, dfs(matrix, i, j - 1) + 1);if(i + 1 < matrix.size() && matrix[i][j] < matrix[i + 1][j])ret = max(ret, dfs(matrix, i + 1, j) + 1);if(j + 1 < matrix[i].size() && matrix[i][j] < matrix[i][j + 1])ret = max(ret, dfs(matrix, i, j + 1) + 1);return ret;}
};

很遗憾，这种做法肯定是超时了，因为这是道困难题，但其实本质就是我们之前说的，有大量重复的问题出现，但是我们都没利用起来，所以考虑使用记忆化搜索来优化！

优化的地方非常的简单了，还是三步走，这里不再赘述，比较简单，具体参考代码，只需要关心注释部分即可，如下所示：

class Solution {
private:int memory[201][201] = { 0 }; // 备忘录
public:int longestIncreasingPath(vector<vector<int>>& matrix) {int ret = 1;for(int i = 0; i < matrix.size(); ++i)for(int j = 0; j < matrix[i].size(); ++j)ret = max(ret, dfs(matrix, i, j));return ret;}int dfs(vector<vector<int>>& matrix, int i, int j){// 进入函数前检查一下备忘录if(memory[i][j] != 0)return memory[i][j];if(i < 0 || i == matrix.size() || j < 0 || j == matrix[i].size())return 0;int ret = 1;if(i - 1 >= 0 && matrix[i][j] < matrix[i - 1][j])ret = max(ret, dfs(matrix, i - 1, j) + 1);if(j - 1 >= 0 && matrix[i][j] < matrix[i][j - 1])ret = max(ret, dfs(matrix, i, j - 1) + 1);if(i + 1 < matrix.size() && matrix[i][j] < matrix[i + 1][j])ret = max(ret, dfs(matrix, i + 1, j) + 1);if(j + 1 < matrix[i].size() && matrix[i][j] < matrix[i][j + 1])ret = max(ret, dfs(matrix, i, j + 1) + 1);// 在离开函数之前添加结果到备忘录memory[i][j] = ret;return ret;}
};