[LeetCode] 329. 矩阵中的最长递增路径(DFS+MEMO)
难度：Hard
题目描述：
解题思路：
用一个Memo记录当前memo[i][j]位置是多少最长路径对棋盘中的每个点进行DFS，当坐标不越界，并且判断的格子是递增的时候:memo[x][y] = max(memo[x][y], dfs(matrix, newX, newY, memo) + 1)
class Solution {
public:
int dx
[4] = {-1, +1, 0, 0};
int dy
[4] = {0, 0, +1, -1};
int row
;
int col
;
int longestIncreasingPath(vector
<vector
<int>>& matrix
) {
if (matrix
.size() == 0 || matrix
[0].size() == 0)
{
return 0;
}
row
= matrix
.size();
col
= matrix
[0].size();
auto memo
= vector
<vector
<int>> (row
, vector
<int>(col
));
int ans
= 0;
for (int i
= 0; i
< row
; i
++)
{
for (int j
= 0; j
< col
; j
++)
{
ans
= max(ans
, dfs(matrix
, i
, j
, memo
));
}
}
return ans
;
}
int dfs(vector
<vector
<int>>& matrix
, int x
, int y
, vector
<vector
<int>>& memo
){
if (memo
[x
][y
] != 0)
{
return memo
[x
][y
];
}
memo
[x
][y
]++;
for (int i
= 0; i
< 4; i
++)
{
int newX
= x
+ dx
[i
];
int newY
= y
+ dy
[i
];
if (newX
>= 0 && newX
< row
&& newY
>= 0 && newY
< col
&& matrix
[newX
][newY
] > matrix
[x
][y
])
{
memo
[x
][y
] = max(memo
[x
][y
], dfs(matrix
, newX
, newY
, memo
) + 1);
}
}
return memo
[x
][y
];
}
};
