地址 https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
给定一个整数矩阵，找出最长递增路径的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。 示例 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 bfs均以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; } };
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; } };
DP解决问题 todo
原文：https://www.cnblogs.com/itdef/p/14312737.html
