329. Longest Increasing Path in a Matrix
Tags:
Hard
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tìm longest increasing path in matrix
Approach
Bài này có thể áp dụng DFS kết hợp memoization để tối ưu hóa
Solution - DFS
SC: O(n * m)
1function longestIncreasingPath(matrix: number[][]): number {
2 let rows = matrix.length;
3 let cols = matrix[0].length;
4
5 const dp: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));
6 const directions = [
7 [-1, 0], [1, 0], [0, -1], [0, 1]
8 ]
9
10 function dfs(r: number, c: number): number {
11 if (dp[r][c] !== 0) return dp[r][c]
12
13 let max_length = 1;
14 for (const [dr, dc] of directions) {
15 const new_row = dr + r;
16 const new_col = dc + c;
17
18 if (
19 new_row >= 0 && new_row < rows &&
20 new_col >= 0 && new_col < cols &&
21 matrix[new_row][new_col] > matrix[r][c]
22 ) {
23 max_length = Math.max(max_length, dfs(new_row, new_col) + 1)
24 }
25 }
26
27 dp[r][c] = max_length;
28 return max_length
29 }
30
31 let res = 0;
32 for (let r = 0; r < rows; r++) {
33 for (let c = 0; c < cols; c++) {
34 res = Math.max(res, dfs(r, c))
35 }
36 }
37
38 return res;
39};