LeetCode 329 矩阵中的最长递增路径(记忆化搜索)

本文主要是介绍LeetCode 329 矩阵中的最长递增路径(记忆化搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度。

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

示例 1:

输入: nums = 
[[9,9,4],[6,6,8],[2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入: nums = 
[[3,4,5],[3,2,6],[2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

思路

首先定义状态。

定义：f[i][j] 表示走到 (i,j) 这个格子的最大长度。

那么枚举这个格子的上下左右，如果新的坐标 (xx,yy) 比这个格低，那么就更新答案。

$f [x] [y] = m a x (f [x] [y], d p (x x, y y) + 1)$

实现的时候使用记忆化搜索来完成。

时间复杂度是： $O(n^2)$

代码

class Solution
{public:int n, m;vector<vector<int>> f, g;int go[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};int dp(int x, int y){if (~f[x][y])return f[x][y];f[x][y] = 1;for (int i = 0; i < 4; i++){int xx = x + go[i][0];int yy = y + go[i][1];if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] < g[x][y])f[x][y] = max(f[x][y], dp(xx, yy) + 1);}return f[x][y];}int longestIncreasingPath(vector<vector<int>> &matrix){if (matrix.empty())return 0;g = matrix;n = g.size(), m = g[0].size();f = vector<vector<int>>(n, vector<int>(m, -1));int res = 0;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)res = max(res, dp(i, j));return res;}
};