题目描述
给定一个整数矩阵,找出最长递增路径的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。
你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
示例 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]。注意不允许在对角线方向上移动。
算法1
这题目和acwing 滑雪 类似
解答先后尝试dfs bfs均以TLE失败
C++ 代码 DFS TLE
class Solution {
public:
int ans = 1;
vector<vector<int>> vis;
void dfs(int x, int y, int step,const vector<vector<int>>& matrix)
{
int m = matrix.size(); int n = matrix[0].size();
int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,1,-1 };
for (int i = 0; i < 4; i++) {
int newx = x + addx[i];
int newy = y + addy[i];
if (newx >= 0 && newx < m && newy >= 0 && newy < n && vis[newx][newy] < (step+1) &&
matrix[x][y] < matrix[newx][newy]) {
int back = vis[newx][newy];
vis[newx][newy] = step + 1;
ans = max(ans, step + 1);
dfs(newx,newy,step+1,matrix);
vis[newx][newy] = back;
}
}
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(); int n = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
vis = vector<vector<int>>(m, vector<int>(n));
vis[i][j] = 1;
dfs(i,j,1,matrix);
}
}
return ans;
}
};
C++ 代码 BFS TLE
class Solution {
public:
queue<vector<int>> q;
vector<vector<int>> vis;
int ans = 1;
void bfs(int x, int y,int m,int n,const vector<vector<int>>& matrix) {
while (!q.empty()) q.pop();
int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,1,-1 };
vis = vector<vector<int>>(m, vector<int>(n));
q.push({x,y,1});
while (!q.empty()) {
int tx = q.front()[0];
int ty = q.front()[1];
int step = q.front()[2]+1;
q.pop();
for (int i = 0; i < 4; i++) {
int newx = tx + addx[i];
int newy = ty + addy[i];
if (newx >= 0 && newx < m&& newy >= 0 && newy < n && matrix[newx][newy] > matrix[tx][ty] &&
vis[newx][newy] < step)
{
vis[newx][newy] = step;
q.push({ newx,newy,step });
ans = max(ans, step);
}
}
}
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(); int n = matrix[0].size();
if (m == 0 || n == 0) return 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
bfs(i,j,m,n, matrix);
}
}
return ans;
}
};
最后考虑记忆化搜索
class Solution {
public:
int ans = 0;
vector<vector<int>> dp;
int dfs(int x, int y, const vector<vector<int>>& matrix) {
if (dp[x][y] != 0) return dp[x][y];
int m = matrix.size(); int n = matrix[0].size();
int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,1,-1 };
for (int i = 0; i < 4; i++) {
int newx = x + addx[i];
int newy = y + addy[i];
if (newx >= 0 && newx < m && newy >= 0 && newy < n && matrix[newx][newy] > matrix[x][y]) {
dp[x][y] = max(dp[x][y], dfs(newx, newy, matrix)+1);
}
}
return dp[x][y];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(); int n = matrix[0].size();
dp = vector<vector<int>>(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = max(ans, dfs(i,j,matrix));
}
}
return ans+1;
}
};