题目描述
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例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]。注意不允许在对角线方向上移动。
题解
DFS+记忆化搜索
拓扑排序
代码
DFS+记忆化搜索（c++）
classSolution { public: intdx[4] = {0, 0, 1, -1}; intdy[4] = {1, -1, 0, 0}; intlongestIncreasingPath(vector<vector<int>>&matrix) { intn=matrix.size(); if (!n) return0; intm=matrix[0].size(); vector<vector<int>>dp(n, vector<int>(m, 0)); intres=1; for (inti=0; i<n; ++i) { for (intj=0; j<m; ++j) { dp[i][j] =dfs(matrix, i, j, dp); res=max(res, dp[i][j]); } } returnres; } intdfs(vector<vector<int>>&matrix, intx, inty, vector<vector<int>>&dp) { if (dp[x][y] >0) returndp[x][y]; intn=matrix.size(), m=matrix[0].size(); dp[x][y] =1; for (inti=0; i<4; ++i) { intnx=x+dx[i], ny=y+dy[i]; if (inside(nx, ny, n, m) &&matrix[nx][ny] <matrix[x] [y]) { dp[x][y] =max(dp[x][y], dfs(matrix, nx, ny, dp)+1); } } returndp[x][y]; } boolinside(intx, inty, intn, intm) { return0<=x&&x<n&&0<=y&&y<m; } };
拓扑排序（c++）
classSolution { public: intdx[4] = {0, 0, 1, -1}; intdy[4] = {1, -1, 0, 0}; intlongestIncreasingPath(vector<vector<int>>&matrix) { intn=matrix.size(); if (!n) return0; intm=matrix[0].size(); vector<vector<int>>dp(n, vector<int>(m, 0)); vector<vector<int>>degree(n, vector<int>(m, 0)); queue<pair<int, int>>Q; for (inti=0; i<n; ++i) { for (intj=0; j<m; ++j) { for (intk=0; k<4; ++k) { intnx=i+dx[k], ny=j+dy[k]; if (inside(nx, ny, n, m) &&matrix[nx][ny] <matrix[i][j]) { degree[i][j]++; } } if (!degree[i][j]) { Q.push({i, j}); dp[i][j] =1; } } } intres=1; while (!Q.empty()) { intx=Q.front().first, y=Q.front().second; Q.pop(); res=max(res, dp[x][y]); for (inti=0; i<4; ++i) { intnx=x+dx[i], ny=y+dy[i]; if (inside(nx, ny, n, m) &&matrix[nx][ny] >matrix[x][y]) { if (!(--degree[nx][ny])) { Q.push({nx, ny}); } dp[nx][ny] =max(dp[nx][ny], dp[x][y]+1); } } } returnres; } boolinside(intx, inty, intn, intm) { return0<=x&&x<n&&0<=y&&y<m; } };
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
