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

如果每一个点dfs，找最大值，这样存在大量的重复搜索。避免重复搜索的办法是用记忆话搜索，用f[i][j]表示从i，j出发的最长路径。很容易推导出转移方程
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
class Solution {
public:
int longestIncreasingPath(vector>& matrix) {
int n = matrix.size();
if(n==0) return 0;
int m = matrix[0].size();
vector> f(n,vector(m,-1));
int res = 0;
for(int i=0;i for(int j=0;j res = max(res,dfs(matrix,f,i,j));
}
}
return res;
}
int dfs(vector>& matrix, vector> &f, int row, int col){
if(f[row][col]!=-1) return f[row][col];
f[row][col] = 1;
for(int i=0;i<4;i++){
int x = row+dx[i];
int y = col+dy[i];
if(x>=0&&x=0&&ymatrix[row][col]){
f[row][col] = max(f[row][col],dfs(matrix,f,x,y)+1);
}
}
return f[row][col];
}
};